1. Lớp 11
  2. Tin học
  3. Chuyên đề Tin Học 11 KNTT Bài 4. Tháp Hà Nội có đáp án

Chuyên đề Tin Học 11 KNTT Bài 4. Tháp Hà Nội có đáp án

251 lượt thi 13 câu hỏi

Đề thi liên quan:

Chuyên đề Tin Học 11 KNTT Bài 1. Đệ quy và hàm đệ quy có đáp án

293 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 2. Thiết kế thuật toán đệ quy có đáp án

285 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 3. Thực hành giải toán theo kĩ thuật đệ quy có đáp án

271 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 5. Thực hành thiết kế thuật toán theo kĩ thuật đệ quy có đáp án

222 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 6. Ý tưởng và kĩ thuật chia để trị có đáp án

273 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 7. Thiết kế thuật toán theo kĩ thuật chia để trị có đáp án

234 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 8. Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị có đáp án

251 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 9. Sắp xếp trộn có đáp án

222 lượt thi

Thi ngay

Chuyên đề Tin Học 11 KNTT Bài 10. Thực hành giải toán bằng kĩ thuật chia để trí có đáp án

220 lượt thi

Thi ngay

Danh sách câu hỏi:

Câu 1:

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,

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 (ảnh 1)
Hình 4.1. Tờ quảng cáo trò chơi “Tháp Hà Nội”, 1883

Câu 2:

Đọ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âu 3:

Mô tả lời giải bài toán với trường hợp n = 1, 2, 3 ở trên (không dùng hình vẽ mô tả)

Câu 4:

Mô tả lời giải bài toán với n = 1, 2, 3 nếu yêu cầu là di chuyển các đĩa từ cọc 1 sang cọc 2 (cọc 3 là cọc trung gian).

Câu 5:

Đọc, trao đổi để hiểu được ý tưởng thiết kế đệ quy cho lời giải bài toán Tháp Hà Nội.

Câu 6:

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).

Câu 7:

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.

Câu 8:

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.

Câu 9:

Viết chương trình đệ quy để tính giá trị H(n) của bài toán Tháp Hà Nội.

Câu 10:

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.

Câu 11:

Viết chương trình rút gọn của hàm Hanoi(n, i, j, k) như sau và kiểm tra kết quả.

Viết chương trình rút gọn của hàm Hanoi(n, i, j, k) như sau và kiểm tra kết quả. (ảnh 1)

Câu 12:

Hãy chứng minh công thức Hn = 2n−1 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.

Câu 13:

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.
4.6

50 Đánh giá

50%

40%

0%

0%

0%

CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
Giấy chứng nhận ĐKKD số: 0108307822 do Sở KH & ĐT TP Hà Nội cấp lần đầu ngày 04/06/2018
© 2017 Vietjack27. All Rights Reserved.

Đăng ký

Bạn đã có tài khoản?