Câu hỏi:

26/06/2024 131

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 trong lớp mà không thể đi xe đạp từ nhà bạn này đến nhà bạn kia. Nếu có thì thông báo tên hai bạn học sinh đó.

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

Để giải quyết vấn đề này, trước hết chúng ta cần xác định liệu có đường đi từ một nhà đến nhà khác không, bằng cách sử dụng hàm find_path mà chúng ta đã viết trước đó. Sau đó, chúng ta sẽ kiểm tra xem có đường đi giữa hai người bạn không.

Dưới đây là cách triển khai trong Python:

def find_unreachable_students(graph):

unreachable_students = [] # Danh sách các bạn học sinh không thể đi xe đạp đến nhau

# Duyệt qua tất cả các cặp học sinh trong lớp

for student1 in graph:

for student2 in graph:

if student1 != student2:

# Kiểm tra xem có đường đi từ nhà của student1 đến nhà của student2 không

path = find_path(graph, student1, student2)

if not path:

unreachable_students.append((student1, student2))

return unreachable_students

# Ví dụ về đồ thị được biểu diễn bằng danh sách kề

graph = {

'Alice': ['Bob', 'Charlie'],

'Bob': ['Alice', 'David', 'Eva'],

'Charlie': ['Alice', 'Frank'],

'David': ['Bob'],

'Eva': ['Bob', 'Frank'],

'Frank': ['Charlie', 'Eva']

}

# Tìm các bạn học sinh không thể đi xe đạp đến nhau

unreachable_students = find_unreachable_students(graph)

if unreachable_students:

print("Có những bạn học sinh không thể đi xe đạp đến nhau:")

for student1, student2 in unreachable_students:

print(student1, "và", student2)

else:

print("Không có bạn học sinh nào không thể đi xe đạp đến nhau.")

- Lưu ý: Trong đoạn mã trên, hàm find_unreachable_students sẽ duyệt qua tất cả các cặp học sinh trong danh sách và kiểm tra xem có đường đi nào giữa họ không. Nếu không có đường đi, họ sẽ được thêm vào danh sách unreachable_students. Sau đó, danh sách này sẽ được in ra để thông báo cho chúng ta biết những học sinh nào không thể đi xe đạp đến nhau.

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

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 đáp án

Lời giải

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

Câu 3