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

penguin

Advertisements

à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

KháchBài viết này chỉ những thành viên có số điểm trên 1  mới xem được, điểm hiện tại của bạn là 0

Thuvienvatly.Com