Nội dung bài viết

    Xem thêm

    Chuyên đề Tin học 12 Bài 5 (Cánh diều): Thực hành duyệt đồ thị

    Với giải bài tập Chuyên đề Tin học 12 Bài 5: Thực hành duyệt đồ thị sách Cánh diều hay nhất, chi tiết giúp học sinh dễ dàng làm bài tập Chuyên đề học tập Tin học 12 Bài 5.

    1 111 13/08/2024
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 12 Bài 5: Thực hành duyệt đồ thị

    Bài toán trang 69 Chuyên đề Tin học 12: Phâ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,....

    Phân nhóm người nghi nhiễm Covid-19 trang 69 Chuyên đề Tin học 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.

    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}')

    Vận dụng trang 69 Chuyên đề Tin học 12: 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 ?

    Bài toán Tìm đường đi trong mê cung trang 69 Chuyên đề Tin học 12

    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.

    Bài toán Tìm đường đi trong mê cung trang 69 Chuyên đề Tin học 12

    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ó.

    Tham khảo các loạt bài Tin học 12 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 111 13/08/2024
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: