Tháp Hà Nội là một bài toán đố. Nơi chúng ta có ba giá đỡ và n đĩa. Ban đầu, Đĩa được đặt ở giá đỡ đầu tiên. Chúng ta phải đặt đĩa vào giá đỡ thứ ba hoặc giá đỡ đích, giá đỡ thứ hai hoặc giá đỡ phụ có thể được sử dụng làm giá đỡ.
- Nhưng có một số quy tắc cần tuân theo.
- Chúng tôi chỉ có thể chuyển một đĩa cho mỗi chuyển động.
- Chỉ có thể lấy đĩa trên cùng từ giá đỡ.
- Không có đĩa lớn hơn sẽ được đặt ở trên cùng của đĩa nhỏ hơn.
Vấn đề này có thể được giải quyết dễ dàng bằng đệ quy. Lúc đầu, sử dụng đệ quy, các đĩa trên cùng (n-1) được đặt từ nguồn đến giá đỡ phụ, sau đó đặt đĩa cuối cùng từ nguồn đến đích, sau đó lại đặt (n-1) đĩa từ giá đỡ phụ đến giá đỡ đích bằng đệ quy.
Đầu vào và Đầu ra
Input: Number of discs: 3 Output: 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ố lượng đĩa, nguồn, phụ, đích.
Đầu ra: Các bước để di chuyển đĩa từ nguồn đến đích duy trì các quy tắc thích hợp.
Begin if n = 1, then display move disc from s to d toh(n-1, s, d, a) display move disc from s to d toh(n-1, a, s, d) End
Ví dụ
#include<iostream>
using namespace std;
void TOH(int n, char s, char a, char d) {
static int count = 0; //store number of counts
if(n == 1) {
count++;
cout << count<< ". Move disk " << n << " from "<<s <<" to "<<d<<endl;
return; //base case, when only one disk
}
TOH(n-1, s, d, a); //recursive call the function
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');
} Đầu ra
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