Câu hỏi:
13/07/2024 61Phân nhóm người nghi nhiễm Covid-19
Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1. Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm FO, những người tiếp xúc với người ở nhóm FO sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm 1-1 sẽ được xếp vào nhóm 12,....
Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19.
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lờ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}')
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Bài toán Tìm đường đi trong mê cung
Nam đang chơi trò chơi tìm đường đi trong mê cung như trong Hình 5. Dùng thuật toán duyệt đồ thị theo chiều sâu đề kiểm tra: Nam có thể đi vào mê cung từ góc trái trên và ra khỏi mê cung ở góc phải dưới hay không ?
về câu hỏi!