Đang chuẩn bị liên kết để tải về tài liệu:
GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - BÀI TẬP CHƯƠNG 6

Bài 1: Di chuyển trên các hình tròn Cho N hình tròn (đánh số từ 1 đến N). Một người muốn đi từ hình tròn này sang hình tròn khác cần tuân theo qui ước: Nếu khoảng cách giữa 2 điểm gần nhất của 2 hình tròn không quá 50 cm thì có thể bước sang. | BÀI TẬP CHƯƠNG 6 ĩ Bài 1 Di chuyển trên các hình tròn Cho N hình tròn đánh số từ 1 đến N . Một người muốn đi từ hình tròn này sang hình tròn khác cần tuân theo qui ước Nếu khoảng cách giữa 2 điểm gần nhất của 2 hình tròn không quá 50 cm thì có thể bước sang. Nếu khoảng cách này hơn 50cm và không quá 80cm thì có thể nhảy sang. Các trường hợp khác không thể sang được. Một đường đi từ hình tròn này sang hình tròn khác đuợc gọi là càng tốt nếu số lần phải nhảy là càng ít. Hai đường đi có số lần nhảy bằng nhau thì đường đi nào có số hình tròn đi qua ít hơn thì đường đi đó tốt hơn. Các hình tròn được cho trong một file văn bản trong đó dòng thứ i mô tả hình tròn số hiệu i i 1 2 . N bao gồm 3 số thực hoành độ tâm tung độ tâm độ lớn bán kính đơn vị đo bằng mét . Lập trình đọc các hình tròn từ một file văn bản tên file vào từ bàn phím sau đó cứ mỗi lần đọc số hiệu hình tròn xuất phát S và hình tròn kết thúc T từ bàn phím chương trình sẽ đưa ra đường đi từ S đến T là tốt nhất theo nghĩa đã nêu hoặc thông báo là không có . Yêu cầu đường đi được viết dưới dạng một dãy các số hiệu hình tròn lần lượt cần được đi qua trong đó nói rõ tổng số các bước nhảy tổng số các hình tròn đi qua và những bước nào cần phải nhảy. Giới hạn sô hình tròn không quá 100. ĩ Bài 2 Tìm hành trình tốn ít xăng nhất Trên một mạng lưới giao thông một người muôn đi từ điểm A đến điểm B bằng xe máy. Xe chứa được tôi đa 3 lít xăng và chạy 100km hết 2 5 lít. Các trạm xăng chỉ được đặt ở các điểm dân cư không đặt ở giữa đường và người này không mang theo bất kỳ thùng chứa xăng nào khác. Hãy viết chương trình nhập vào mạng lưới giao thông và xác định giúp người này tuyến đường đi từ A đến B sao cho ít tôn xăng nhất. Bài 3 Di chuyển giữa các đảo Trên một đảo quôc có N hòn đảo. Giả sử tất cả các đảo đều có hình dạng là hình chữ nhật nằm ngang. Trên mỗi hòn đảo có thể có sân bay nằm ở trung tâm đảo có thể có cảng nằm ở 4 góc đảo. Trên mỗi đảo đều có tuyến đường xe buýt nôi 4 góc đảo với nhau và với trung tâm đảo. .