Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí

Giải Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu - Kết nối tri thức

Vận dụng 1 trang 74 Chuyên đề Tin học 12: Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí thì thông báo dãy các chuyên đề có mâu thuẫn về kiến thức.

Lời giải:

Phiên bản mẫu gợi ý sửa đổi của chương trình để bổ sung thông báo nếu hệ thống chuyên đề không hợp lý và hiển thị dãy các chuyên đề có mâu thuẫn về kiến thức:

def DFS(graph, start, visited, stack):

    visited[start] = True

    for neighbor in graph[start]:

        if not visited[neighbor]:

            DFS(graph, neighbor, visited, stack)

    stack.append(start)

def topological_sort(graph):

    num_nodes = len(graph)

    visited = [False] * num_nodes

    stack = []

    for node in range(num_nodes):

        if not visited[node]:

            DFS(graph, node, visited, stack)

    return stack[::-1]

def is_valid_system(topological_order, prerequisites):

    knowledge = set()

    for course in topological_order:

        knowledge.add(course)

        if course in prerequisites:

            for prerequisite in prerequisites[course]:

                if prerequisite not in knowledge:

                    return False, [course, prerequisite]

    return True, None

def check_course_system(prerequisites):

    graph = {}

    for course, prereq in prerequisites.items():

        if course not in graph:

            graph[course] = []

        graph[course].extend(prereq)

    topological_order = topological_sort(graph)

    valid, conflicting_topics = is_valid_system(topological_order, prerequisites)

    if valid:

        print("Hệ thống chuyên đề hợp lý.")

    else:

        print("Hệ thống chuyên đề không hợp lý.")

        print("Dãy các chuyên đề có mâu thuẫn về kiến thức:", conflicting_topics)

# Dữ liệu chuyên đề và tiên điều kiện

prerequisites = {

    "A": ["B"],

    "B": ["C"],

    "C": ["D"],

    "D": ["A"]  # Mâu thuẫn về kiến thức với tiên điều kiện của D

}

# Kiểm tra hệ thống chuyên đề

check_course_system(prerequisites)

Lời giải bài tập Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu hay, ngắn gọn khác:

• Khởi động trang 72 Chuyên đề Tin học 12: Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường ....

• Luyện tập 1 trang 74 Chuyên đề Tin học 12: Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu ....

• Luyện tập 2 trang 74 Chuyên đề Tin học 12: Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình ....

• Vận dụng 2 trang 74 Chuyên đề Tin học 12: Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---