Câu hỏi:
11/05/2023 195
Năm 1883, tại một số tỉnh thành của Việt Nam và tại Pháp xuất hiện một trò chơi được quảng cáo với tên “Tháp Hà Nội” (La tour d’Hanoi). Trò chơi này được bán rộng rãi và theo một tờ quảng cáo vào thời gian đó là sẽ trao giải hàng triệu francs cho ai có thể giải được tất cả các mức từ thấp đến cao nhất là 64 đĩa. Trong tờ rơi đó cũng đưa ra con số 18446744073709551615 bước chuyển cho trường hợp 64 đĩa và khuyến cáo rằng sẽ cần hàng tỉ năm để giải được trò chơi này. Trò chơi như sau: có ba cái cọc (ví dụ cọc 1, 2, 3) và n cái đĩa được xếp tại cọc 1 theo thứ tự to dần từ trên xuống. Yêu cầu chuyển n đĩa này sang cọc 3 với điều kiện là được dùng cọc 2 làm trung gian, mỗi lần chỉ được phép chuyển 1 đĩa và không cho phép đặt đĩa to chồng lên đĩa nhỏ.
Em hãy suy nghĩ và thử giải trò chơi trên với n = 1,
Hình 4.1. Tờ quảng cáo trò chơi “Tháp Hà Nội”, 1883
Năm 1883, tại một số tỉnh thành của Việt Nam và tại Pháp xuất hiện một trò chơi được quảng cáo với tên “Tháp Hà Nội” (La tour d’Hanoi). Trò chơi này được bán rộng rãi và theo một tờ quảng cáo vào thời gian đó là sẽ trao giải hàng triệu francs cho ai có thể giải được tất cả các mức từ thấp đến cao nhất là 64 đĩa. Trong tờ rơi đó cũng đưa ra con số 18446744073709551615 bước chuyển cho trường hợp 64 đĩa và khuyến cáo rằng sẽ cần hàng tỉ năm để giải được trò chơi này. Trò chơi như sau: có ba cái cọc (ví dụ cọc 1, 2, 3) và n cái đĩa được xếp tại cọc 1 theo thứ tự to dần từ trên xuống. Yêu cầu chuyển n đĩa này sang cọc 3 với điều kiện là được dùng cọc 2 làm trung gian, mỗi lần chỉ được phép chuyển 1 đĩa và không cho phép đặt đĩa to chồng lên đĩa nhỏ.
Em hãy suy nghĩ và thử giải trò chơi trên với n = 1,
Hình 4.1. Tờ quảng cáo trò chơi “Tháp Hà Nội”, 1883
Câu hỏi trong đề:
Chuyên đề Tin Học 11 KNTT Bài 4. Tháp Hà Nội có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?
Với n = 2, ta có hai cái đĩa, ta sẽ di chuyển đĩa lớn nhất từ cọc 1 sang cọc trung gian 2, sau đó di chuyển đĩa nhỏ từ cọc 1 sang cọc đích 3, và cuối cùng di chuyển đĩa lớn từ cọc 2 sang cọc đích 3
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4).
Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4).
Xem đáp án »
12/07/2024
630
Câu 2:
Hãy chứng minh công thức bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.
Hãy chứng minh công thức bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.
Xem đáp án »
12/07/2024
407
Câu 3:
Tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội.
Tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội.
Xem đáp án »
12/07/2024
343
Câu 4:
Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?
Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?
Xem đáp án »
11/05/2023
305
Câu 5:
Viết chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C.
Viết chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C.
Xem đáp án »
12/07/2024
228
Câu 6:
Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j lấy cọc k làm trung gian. Các đĩa được đánh số từ 1 đến n và xếp theo thứ tự từ trên xuống. Các điều kiện của việc chuyển như sau:
1. Các đĩa đánh số từ 1 đến n và có kích thước tăng dần.
2. Mỗi lần chỉ được phép chuyển một đĩa.
3. Không được phép xếp đĩa to lên trên đĩa nhỏ.
Em hãy thiết kế thuật toán đệ quy tổng quát cho bài toán trên. Yêu cầu phải mô tả chi tiết từng bước chuyển.
Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j lấy cọc k làm trung gian. Các đĩa được đánh số từ 1 đến n và xếp theo thứ tự từ trên xuống. Các điều kiện của việc chuyển như sau:
1. Các đĩa đánh số từ 1 đến n và có kích thước tăng dần.
2. Mỗi lần chỉ được phép chuyển một đĩa.
3. Không được phép xếp đĩa to lên trên đĩa nhỏ.
Em hãy thiết kế thuật toán đệ quy tổng quát cho bài toán trên. Yêu cầu phải mô tả chi tiết từng bước chuyển.
Xem đáp án »
11/05/2023
217
Câu 7:
Giả sử cần lưu dãy các bước chuyển của bài toán Tháp Hà Nội vào một danh sách để có thể sử dụng lại về sau. Mỗi bước chuyển dạng k: i → j sẽ được lưu trong một bộ ba số (k, i, j). Viết chương trình giải bài toán Tháp Hà Nội tổng quát Hanoi(n, i, j, k) chuyển n đĩa từ cọc i sang cọc j lấy cọc k làm trung gian với yêu cầu lưu tất cả các bước chuyển vào một danh sách (list). Như vậy, hàm Hanoi(n, i, j, k) sẽ trả về một danh sách bao gồm các bộ ba số dạng như đã mô tả ở trên.
Giả sử cần lưu dãy các bước chuyển của bài toán Tháp Hà Nội vào một danh sách để có thể sử dụng lại về sau. Mỗi bước chuyển dạng k: i → j sẽ được lưu trong một bộ ba số (k, i, j). Viết chương trình giải bài toán Tháp Hà Nội tổng quát Hanoi(n, i, j, k) chuyển n đĩa từ cọc i sang cọc j lấy cọc k làm trung gian với yêu cầu lưu tất cả các bước chuyển vào một danh sách (list). Như vậy, hàm Hanoi(n, i, j, k) sẽ trả về một danh sách bao gồm các bộ ba số dạng như đã mô tả ở trên.
Xem đáp án »
12/07/2024
208
Bình luận
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 11: Cơ sở dữ liệu có đáp án
-
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 10: Lưu trữ dữ liệu và khai thác thông tin phục vụ quản lí có đáp án
-
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 12: Hệ quản trị cơ sở dữ liệu và hệ cơ sở dữ liệu có đáp án
-
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 3)
-
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 13: Cơ sở dữ liệu quan hệ có đáp án
-
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 1)
-
15 câu Trắc nghiệm Tin học 11 KNTT Tin học ứng dụng Bài 14: SQL – Ngôn ngữ truy vấn có cấu trúc có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Tin học ứng dụng Bài 1: Bài toán quản lý và cơ sở dữ liệu có đáp án
về câu hỏi!