Giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C/C++

Sắp xếp các đĩa vàng theo quy tắc

Trước khi tìm hiểu cách giải bài toán Tháp Hà Nội (Tower of Hanoi), chúng ta cần làm quen với các quy tắc của trò chơi này. Bài toán Tháp Hà Nội bao gồm 3 cột và số lượng đĩa lớn hơn 1.

Bài toán tháp Hà Nội

Quy tắc là các đĩa càng nhỏ phải nằm trên đĩa lớn. Dù số lượng đĩa khác nhau, cách giải vẫn giữ nguyên.

Qui tắc trò chơi Tháp Hà Nội

Nhiệm vụ của trò chơi này là di chuyển các đĩa có kích thước khác nhau sang cột khác với điều kiện vẫn duy trì thứ tự ban đầu: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc:

Hình ảnh dưới đây mô tả cách giải bài toán Tháp Hà Nội. Tháp Hà Nội

Mục đích của bài toán là hoàn thành yêu cầu của trò chơi. Bài toán thông thường là: "Bạn được cho ba cái cọc và một số đĩa có kích thước khác nhau, và bạn sắp xếp các đĩa này theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng. Bạn phải di chuyển toàn bộ các đĩa sang một cọc khác, tuân theo các quy tắc sau:

• Mỗi lần chỉ di chuyển một đĩa.
• Chỉ được đặt đĩa lên một đĩa lớn hơn."

Bài toán Tháp Hà Nội với n đĩa có ít nhất 2^n - 1 bước di chuyển. Ví dụ, với 3 đĩa, ta cần ít nhất 2^3-1=7 bước để giải bài toán.

Cách giải bài toán Tháp Hà Nội bằng phương pháp đệ quy

Qui ước: Đặt tên 3 cột là A, B, và C để dễ theo dõi. Yêu cầu của bài toán là chuyển n chiếc đĩa từ cột A sang cột C.

Cách giải:

1. Đầu tiên, chúng ta lấy cột C làm cọc trung gian và chuyển n-1 chiếc đĩa sang cột B.
2. Tiếp theo, chúng ta chuyển chiếc đĩa lớn nhất sang cột C.
3. Cuối cùng, chúng ta lấy cột A làm cột trung gian và chuyển n-1 chiếc đĩa từ cột B sang cột C.

Hình ảnh dưới đây mô tả cách giải bài toán Tháp Hà Nội. Cách giải bài toán tháp Hà Nội

Dưới đây là đoạn code trong C++:

#include
using namespace std;

void Tower(int n , char a, char b, char c ){
   if(n==1){
      cout<<"t"<>n;
   Tower(n,a,b,c);
}

Đoạn code trong C:

#include

void Tower(int n , char a, char b, char c ){
   if(n==1){
      printf("t%c-%cn",a,c);
      return;
   }
   Tower(n-1,a,c,b);
   Tower(1,a,b,c);
   Tower(n-1,b,a,c);
}

int main(){
   char a='A', b='B', c='C';
   int n;
   printf("Nhap n: ");
   scanf("%d",&n);
   Tower(n,a,b,c);
}

Bài viết chỉ đến đây là kết thúc. Cảm ơn các bạn đã theo dõi!