Giải chuyên đề Tin 12 Cánh diều Bài 5: Thực hành duyệt đồ thị có đáp án
11 người thi tuần này 4.6 402 lượt thi 2 câu hỏi
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Dành cho bạn Hot
Trắc nghiệm Tính đơn điệu và cực trị của hàm số lớp 12 (có đáp án - phần 1)
Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)
Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án
10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án
20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án
20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án
15 câu Trắc nghiệm Tin học 12 Bài 1. Làm quen với Trí tuệ nhân tạo (có đáp án)
15 câu Trắc nghiệm KTPL 12 Bài 1 (có đáp án)
Danh sách câu hỏi:
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Dùng măng hàng đợi Q đề thăm các đỉnh theo chiều rộng, máng level để ghi nhận nhóm nghi nhiễm, Hình 2, 3, 4 mô tá ba bước đầu tiên trong quá trình thực hiện.
Mã giả để thực hiện nhiệm vụ phân nhóm người nghi nhiễm COVID-19 bằng thuật toán duyệt đồ thị theo chiều rộng (BFS):
from collections import deque
# Biểu diễn đồ thị bằng danh sách kề
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4, 5],
3: [1, 6],
4: [2],
5: [2],
6: [3]
}
# Hàm thực hiện BFS để phân nhóm
def bfs_covid_contact_tracing(graph, start):
# Khởi tạo hàng đợi và danh sách nhóm
queue = deque([start])
levels = {start: 'FO'} # Người 0 thuộc nhóm FO
visited = {start}
# Duyệt đồ thị
while queue:
vertex = queue.popleft()
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# Phân nhóm dựa trên nhóm của người tiếp xúc
levels[neighbour] = 'F1' if levels[vertex] == 'FO' else 'F2'
return levels
# Gọi hàm và in kết quả
levels = bfs_covid_contact_tracing(graph, 0)
for person, level in levels.items():
print(f'Người {person} thuộc nhóm {level}')
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Xây dựng đồ thị, đánh số các ô trong mê cung (Hình 6), mỗi ô tương ứng
một đỉnh của đồ thị, hai ô kể cạnh có cạnh nối. Theo như Hình 6, đồ thị có 50 đỉnh. Duyệt đồ thị theo chiều sâu bắt đầu từ ô số 1 theo thứ tự ưu tiên đi theo ô xuống dưới, sang phải, lên trên, sang trái.

Mã giả để giải bài toán tìm đường đi trong mê cung sử dụng thuật toán duyệt đồ thị theo chiều sâu (DFS):
def dfs(maze, start, end):
stack = [(start, [start])]
visited = set()
while stack:
(vertex, path) = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
for neighbor in get_neighbors(maze, vertex):
if neighbor == end:
return path + [end]
stack.append((neighbor, path + [neighbor]))
return None
def get_neighbors(maze, cell):
# Giả sử hàm này trả về danh sách các ô kề cạnh có thể đi được từ ô hiện tại
pass
# Giả sử maze là một mảng hai chiều biểu diễn mê cung, start và end là vị trí bắt đầu và kết thúc
path = dfs(maze, start, end)
if path:
print("Có đường đi từ góc trái trên đến góc phải dưới.")
else:
print("Không có đường đi.")
Lưu ý:
Cần xác định cấu trúc dữ liệu maze phù hợp và viết hàm get_neighbors để lấy các ô kề cạnh có thể đi được từ một ô bất kỳ trong mê cung. Mã giả trên chỉ là khung sườn cơ bản, bạn cần điều chỉnh để phù hợp với dữ liệu cụ thể của bài toán bạn đang giải quyết. Đồ thị mê cung cụ thể cần được xây dựng dựa trên hình ảnh mê cung bạn có.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.

