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.
II. MỘT SỐ KHÁI NIỆM, ĐỊNH LÍ, BỔ ĐỀ SỬ DỤNG TRONG PHẠM VI TÀI LIỆU NÀY
...
Mời download file tại: https://thuvienvatly.com/download/12184
