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
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: