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
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 đó.
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 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 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 đó.
Lời giải:
Để 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.
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: