Bài toán Tháp Hà Nội (Tower Of Hanoi)

Giới thiệu

Tháp Hà Nội là một bài toán đố. Có ba cọc và n đĩa. Ban đầu, các đĩa được đặt ở cọc thứ nhất. Ta phải đặt các đĩa vào cọc thứ ba hoặc cọc đích, cọc thứ hai hoặc cọc phụ có thể dùng làm cọc hỗ trợ.

Nhưng có một số quy tắc phải tuân theo:

• Chỉ được chuyển một đĩa cho mỗi lần di chuyển.
• Chỉ đĩa trên cùng mới có thể nhấc lên từ một cọc.
• Không được đặt đĩa to hơn lên trên đĩa nhỏ hơn.

Bài toán này có thể giải quyết dễ dàng bằng đệ quy. Trước tiên, dùng đệ quy đặt (n-1) đĩa trên cùng từ cọc nguồn sang cọc phụ, sau đó đặt đĩa cuối cùng từ cọc nguồn sang cọc đích, rồi lại đặt (n-1) đĩa từ cọc phụ sang cọc đích bằng đệ quy.

Đầu vào và Đầu ra

Đầu vào: Số đĩa: 3
Đầu ra:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

Thuật toán

toh(n, s, a, d)
Đầu vào: Số đĩa, nguồn, phụ, đích.
Đầu ra: Các bước di chuyển đĩa từ nguồn đến đích tuân thủ quy tắc.

Begin
    if n = 1, then
        hiển thị di chuyển đĩa từ s đến d
    toh(n-1, s, d, a)
    hiển thị di chuyển đĩa từ s đến d
    toh(n-1, a, s, d)
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
    static int count = 0;  // lưu số lượng bước
    if(n == 1) {
        count++;
        cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
        return;  // trường hợp cơ sở, khi chỉ còn một đĩa
    }
    TOH(n-1, s, d, a);  // gọi đệ quy hàm
    count++;
    cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
    TOH(n-1, a, s, d);
}

int main() {
    int n;
    cout << "Enter the number of disks: "; cin >> n;
    TOH(n, 'A', 'B', 'C');
}

Kết quả

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C