Giải thuật mới ở trò chơi bài toán THÁP HÀ NỘI - Giải nhất ISEF 2011

Tài liệu này sẽ trình bày xung quanh thuật toán khử đệ quy để chơi bài toán Tháp Hà Nội 3 cột trên phương diện thực hành và đề xuất thuật giải tổng quát mới dành cho trường hợp có bốn cột trở lên…

Giải thuật mới ở trò chơi – bài toán THÁP HÀ NỘI

Người thực hiện: Vương Thiện Huy – lớp 11D1 Trường TH Thực hành ĐHSP TP.HCM

GVHD: Đỗ Công Đoán

Tác giả, Vương Thiện Huy, thứ hai từ phải qua, trong buổi lễ trao giải, các em còn lại đạt giải nhì và khuyến khích

I. BÀI TOÁN THÁP HÀ NỘI (Được Lucas đề xuất năm 1883)

Bài toán này như sau:

Cho n đĩa đánh số từ 1 đến n, có đường kính tăng dần theo chỉ số (số thứ tự đĩa), xếp n đĩa này vào cột thứ nhất, gọi là “cột nguồn” (‘POSITION 0’ trên hình), tạo thành một ‘hình nón’. Nhiệm vụ của người giải là chuyển hết ‘nón’ này từ cột thứ nhất sang cột thứ ba, gọi là cột đích (‘POSITION 2’ trên hình); dùng cột thứ hai (‘POSITION 1’) làm cột “trung chuyển”, sao cho phải thoả mãn 2 điều kiện

Thứ nhất, mỗi lần chỉ di chuyển được 1 cái đĩa

Thứ hai, một đĩa chỉ được đặt vào một cột rỗng (chưa có đĩa nào) hay chỉ được đặt trên đĩa lớn hơn (chẳng hạn đĩa 2 được phép đặt lên trên đĩa 4 nhưng không được đặt lên đĩa 1).

Đặt d là số đĩa cần chuyển từ cột 1 sang cột 3 trong Bài toán THÁP HÀ NỘI.

Bài trước | Bài kế tiếp