Thiết lập hàm printpath s,t không đệ quy có tính năng tương tự hàm cùng tên trong chương trình trên

Giải Chuyên đề Tin 12 Bài 17: Thực hành duyệt đồ thị tổng hợp - Kết nối tri thức

Vận dụng 2 trang 82 Chuyên đề Tin học 12: Thiết lập hàm printpath(s,t) không đệ quy có tính năng tương tự hàm cùng tên trong chương trình trên.

Lời giải:

Phiên bản không đệ quy của hàm printpath(s, t) bằng cách sử dụng một vòng lặp thay vì đệ quy:

def printpath(s, t):

    if t == s:

        print(names[s], end="")

        return

    path = []

    current = t

    while current != s:

        if prev[current] == None:

            print("Không tồn tại đường đi")

            return

        path.append(names[current])

        current = prev[current]

    path.append(names[s])

    path.reverse()

    print(" -> ".join(path), end=" ")

# Đoạn mã dưới đây mô phỏng dữ liệu của biến names và prev

names = ["A", "B", "C", "D", "E"]

prev = [None, 0, 1, 0, 2]

# Sử dụng hàm printpath

printpath(0, 4)  # Mô phỏng đường đi từ đỉnh 0 đến 4

- Chú ý: Trong hàm này, chúng ta sử dụng một vòng lặp để lặp lại từ đỉnh đích t đến đỉnh nguồn s, và trong quá trình này, chúng ta xây dựng một danh sách đường đi. Sau đó, chúng ta đảo ngược danh sách này và in ra. Nếu không có đường đi từ s đến t, chúng ta in ra thông báo "Không tồn tại đường đi".

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

• Khởi động trang 80 Chuyên đề Tin học 12: Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán ....

• Luyện tập 1 trang 82 Chuyên đề Tin học 12: Sửa lại phần nhập dữ liệu hai học sinh: sẽ nhập trực tiếp tên hai học sinh, kiểm tra các tên ....

• Luyện tập 2 trang 82 Chuyên đề Tin học 12: Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A ....

• Vận dụng 1 trang 82 Chuyên đề Tin học 12: Bổ sung thêm yêu cầu của nhiệm vụ trên như sau: Có hay không hai bạn học sinh ....

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 15: Thực hành 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

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

---