Bài toán Tháp Hà Nội (Tower of Hanoi)
Tháp Hà Nội (Tower of Hanoi) là gì?
Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.
Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.
Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)
Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):
Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.
Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1
. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7
bước.
Giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi)
Để viết giải thuật cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi), đầu tiên chúng ta cần tìm hiểu cách giải bài toán với số đĩa là 1 và 2. Chúng ta gán 3 cột với các tên là:
cotNguon: cột ban đầu chứa các đĩa
cotDich: cột cần di chuyển các đĩa tới
cotTrungGian: cột trung gian có mục đích làm trung gian trong quá trình di chuyển đĩa
Nếu chỉ có 1 đĩa, chúng ta chỉ cần di chuyển từ cotNguon tới cotDich.
Nếu có 2 đĩa:
Đầu tiên chúng ta di chuyển đĩa trên cùng (đĩa nhỏ nhất) tới cotTrungGian.
Sau đó chúng ta di chuyển đĩa ở dưới cùng (đĩa to hơn) tới cotDich.
Và cuối cùng di chuyển đĩa nhỏ nhất từ cotTrungGian về cotDich.
Từ hai giải thuật phần giải thuật trên chúng ta sẽ có giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi) cho 3 đĩa trở lên. Chúng ta chia ngăn xếp các đĩa thành hai phần: đĩa thứ lớn nhất (đĩa thứ n) là phần thứ nhất và (n-1) đĩa còn lại là phần thứ hai.
Mục đích của chúng ta là di chuyển đĩa thứ n từ cotNguon tới cotDich và sau đó đặt tất cả (n-1) đĩa còn lại lên trên nó. Bây giờ chúng ta có thể tưởng tượng ra cách giải bài toán trên dựa vào đệ qui theo các bước sau:
Bước 1: Di chuyển n-1 đĩa từ cotNguon tới cotTrungGian Bước 2: Di chuyển đĩa thứ n từ cotNguon tới cotDich Bước 3: Di chuyển n-1 đĩa từ cotTrungGian về cotDich
Giải thuật đệ qui cho bài toán Tháp Hà Nội (Tower of Hanoi) là:
Bắt đầu giải thuật Tháp Hà nội Hanoi(disk, cotNguon, cotDich, cotTrungGian) IF disk == 0, thì di chuyển đĩa từ cotNguon tới cotDich ELSE Hanoi(disk - 1, cotNguon, cotTrungGian, cotDich) // Bước 1 di chuyển đĩa từ cotNguon tới cotDich // Bước 2 Hanoi(disk - 1, cotTrungGian, cotDich, cotNguon) // Bước 3 Kết thúc IF Kết thúc giải thuật
Theo Tutorialspoint
Bài trước: Khái niệm cơ bản về đệ qui (Recursion)
Bài tiếp: Dãy Fibonacci trong Cấu trúc dữ liệu và giải thuật
Bạn nên đọc
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Căn bậc 2, cách tính căn bậc 2
-
Số thập phân là gì? Các phép tính với số thập phân
-
Trực tâm là gì? Xác định trực tâm trong tam giác
-
Công thức tính chiều cao hình thang: thường, vuông, cân
-
Số chính phương là gì? Cách nhận biết và ví dụ chi tiết
- Code NgầuThích · Phản hồi · 6 · 17/08/20
Cũ vẫn chất
-
Kiểu dữ liệu trong Python: chuỗi, số, list, tuple, set và dictionary
Hôm qua 4 -
Code Rồng Thần AFK mới nhất và cách nhập
Hôm qua -
Giải phương trình bậc 2 một ẩn bằng Python
Hôm qua 3 -
Mẹo chơi Rent Please! Landlord Sim cho người mới
Hôm qua 1 -
6 lý do nên chuyển sang Microsoft Edge thay vì dùng Google Chrome
Hôm qua -
Cách xóa bất cứ chi tiết nào trong ảnh với GIMP
Hôm qua -
Hướng dẫn cài Windows 11, cài Win 11 bằng file ISO
Hôm qua 17 -
Hướng dẫn nhận voucher Viettel chào năm mới 2024
Hôm qua -
Loli là gì? BB là gì?
Hôm qua 2 -
Code Bathroom Tower Defense mới nhất và cách nhập code
Hôm qua