Câu hỏi:

11/07/2024 149

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 có áp dụng thuật toán duyệt đồ thị theo chiều sâu. Còn về thuật toán duyệt theo chiều rộng em có biết gì về các ứng dụng thực tế của bài toán này không?

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 17: Thực hành duyệt đồ thị tổng hợp có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search) cũng rất hữu ích và được sử dụng trong nhiều ứng dụng thực tế. Dưới đây là một số ứng dụng phổ biến của BFS:

- Tìm kiếm ngắn nhất trong đồ thị không có trọng số

- Tìm kiếm ngắn nhất trong mạng lưới (grid)

- Tìm kiếm trạng thái

- Tính toán khoảng cách

- Kiểm tra tính liên thông của đồ thị

- Tìm kiếm trong cấu trúc dữ liệu cây

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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 này có nhập đúng không và thực hiện yêu cầu như trong chương trình trên.

Xem đáp án

Lời giải

Để sửa lại phần nhập dữ liệu để nhập trực tiếp tên hai học sinh và kiểm tra tính hợp lệ của chúng, chúng ta có thể thực hiện như sau:

Bài mẫu tổng quát gợi ý:

def input_student_names():

while True:

name1 = input("Nhập tên học sinh thứ nhất: ")

name2 = input("Nhập tên học sinh thứ hai: ")

if name1.strip() == "" or name2.strip() == "":

print("Tên học sinh không được để trống. Vui lòng nhập lại.")

elif name1 == name2:

print("Hai học sinh không thể có cùng tên. Vui lòng nhập lại.")

else:

return name1, name2

# Hàm tính tổng điểm trung bình

def calculate_average_score(score_list):

return sum(score_list) / len(score_list)

# Hàm in thông tin học sinh

def print_student_info(name, scores):

avg_score = calculate_average_score(scores)

print(f"Học sinh {name}:")

print(f" - Điểm Toán: {scores[0]}")

print(f" - Điểm Văn: {scores[1]}")

print(f" - Điểm Anh: {scores[2]}")

print(f"Điểm trung bình: {avg_score:.2f}")

# Hàm nhập điểm cho học sinh

def input_student_scores(name):

scores = []

for subject in ["Toán", "Văn", "Anh"]:

while True:

try:

score = float(input(f"Nhập điểm {subject} của học sinh {name}: "))

if score < 0 or score > 10:

print("Điểm phải nằm trong khoảng từ 0 đến 10. Vui lòng nhập lại.")

else:

scores.append(score)

break

except ValueError:

print("Điểm phải là một số thực. Vui lòng nhập lại.")

return scores

# Hàm chính

def main():

print("Nhập thông tin của hai học sinh:")

name1, name2 = input_student_names()

scores1 = input_student_scores(name1)

scores2 = input_student_scores(name2)

print("\nThông tin hai học sinh sau khi nhập:")

print_student_info(name1, scores1)

print()

print_student_info(name2, scores2)

if __name__ == "__main__":

main()

- Trong phiên bản này, chúng ta sử dụng một vòng lặp while để yêu cầu người dùng nhập tên hai học sinh. Sau đó, kiểm tra tính hợp lệ của tên đó (không được để trống và hai học sinh không thể có cùng tên). Nếu các tên được nhập đúng cách, chúng ta trả về tên của hai học sinh và tiếp tục với việc nhập điểm và in thông tin học sinh như bình thường.

Câu 2

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.

Xem đáp á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".