Sử dụng đệ quy để giải bài toán tháp Hà Nội

Trong bài viết này, codehow sẽ hướng dẫn các bạn sử dụng đệ quy để giải bài toán tháp Hà Nội. Đây là một bài toán khá nổi tiếng, vậy làm thế nào để giải nó bằng cách sử dụng đệ quy thì bài viết này sẽ trả lời cho bạn nhé.

Trước khi đi vào thuật toán giải bài toán, chúng ta cần hiểu bài toán Hà Nội là gì? Và tính chất của nó đã nhé.

Bài toán tháp Hà Nội là gì?

Từ lâu thì bài toán tháp Hà Nội đã làm khó biết bao nhiêu thế hệ học sinh. Bởi để thành thạo được quy luật giải của nó không phải ai cũng có thể làm được. Công việc đơn giản của nó là dịch chuyển các đĩa từ cột này sang cột kia mà thôi.

Trò chơi bao gồm các đĩa với kích thước khác nhau, tùy vào độ khó của bài toán sẽ có bao nhiêu chiếc đĩa. Mỗi đĩa được đục một lỗ tròn ở giữa và nằm xuyên giữa ba cái cột. Ban đầu các đĩa này được xếp vào một cột theo hình nón, nghĩa là đĩa to nằm dưới, dĩa nhỏ nằm trên.

Yêu cầu làm sao để di chuyển các đĩa từ cột này sang cột khác mà tuân theo quy luật dưới đây:

• Chỉ có ba cột để di chuyển (như hình trên).
• Chỉ di chuyển duy nhất một đĩa trên cùng mỗi lần.
• Đĩa nhỏ hơn phải đặt trên đĩa lớn lơn, không được đặt ngược lại.

Ý tưởng giải bài toán tháp Hà Nội bằng đệ quy

Quy luật trò chơi ta đã có, dựa vào đó ta sẽ áp dụng đệ quy để giải bài toán này.

Đầu tiên chúng ta cần quan tâm đến số đĩa N, cột A, cột B, cột C. Nhiệm vụ của chúng ta lúc này là chuyển N lần sao cho số đĩa ở cột A sang hết cột C và cột B là cột tạm thời.

Thuật toán:

• Nếu chúng ta có cách chuyển N - 1 từ cột A sang cột B. Khi đó ta chuyển đĩa N từ cột A sang thằng cột C, sau đó chuyển N - 1 từ cột B sang cột C.
• Giải thuật sẽ không gọi đệ quy nếu chỉ còn một đĩa duy nhất. Khi đó nó chuyển thằng từ cột A sang cột C luôn mà không cần thông qua B.
• Độ phức tạp của thuật toán là 2ⁿ - 1 (lần dịch chuyển).

Bây giơ chúng ta sẽ áp dụng thuật toán vào việc viết chương trình giải bài toán tháp Hà Nội nhé.

Giải bài toán tháp Hà Nội sử dụng đệ quy trong C / C++

Dựa vào ý tưởng ở phần hai, mình có giải thuật để giải bài toán tháp Hà Nội dưới đây. Các bạn xem qua sau đó mình sẽ giải thích ngay bên dưới nhé.

void move(int n,char A,char B,char C)
 {
      if(n==1){
        cout<<A<<" ==> "<<C<<"\n";// nếu n = 1 thì dịch chuyển từ A -> C
      }
      else {        
        // Nếu n > 1 thì thực hiện lần lượt các bước
        move(n - 1, A, C, B); // 1. Dịch chuyển n-1 đĩa từ A -> B
        cout<<A<<" ==> "<<C<<"\n"; // 2. Dịch chuyển đĩa thứ n từ A -> C
        move(n - 1, B, A, C); // 3. Dịch chuyển n-1 đĩa từ B -> C
      }
 }

Giải thích:

• Nếu n == 1 thì chúng ta chỉ cần chuyển thằng đĩa từ cột A sang cột C.
• Nếu n > 1, thì chúng ta cần thực hiện ba giai đoạn.
  • Chuyển n - 1 đĩa từ cột A sang cột B -> move(n-1, A, B, C).
  • Chuyển đĩa còn lại (đĩa n) từ cột A sang thằng cột C.
  • Chuyển n - 1 đĩa từ cột B sang cột C -> move(n-1, B, A, C).

Giả sử mình có n = 3 (số đĩa bằng 3) thì số lần thực hiện bằng 2³ - 1 = 7 (lần).

Dưới đây là hai chương trình sử dụng đệ quy để giải bài toán tháp Hà Nội mình đã viết. Chương trình được viết bằng hai ngôn ngữ khác nhau là C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>

void move(int n,char A,char B,char C)
 {
      if(n==1){
        printf("%c ==> %c\n",A,C);// nếu n = 1 thì dịch chuyển từ A -> C
      }
      else {        
        //// Nếu n > 1 thì thực hiện lần lượt các bước
        move(n - 1, A, C, B); // 1. Dịch chuyển n-1 đĩa từ A -> B
        printf("%c ==> %c\n",A,C); //2. Dịch chuyển đĩa thứ n từ A -> C
        move(n - 1, B, A, C); // 3. Dịch chuyển n-1 đĩa từ B -> C
      }
 }


int main() {
  int n;
  printf("\nNhập vào số đĩa N mà bạn muốn tìm cách giải: ");
  scanf("%d", &n);
  printf("Thứ tự dịch chuyển các vị trí A B C là: \n");
  move(n, 'A', 'B', 'C');
 
  printf("\n---------------------------\n");
  printf("Chương trình này được đăng tại codehow.net");
}

Chương trình C++:

#include <iostream>
using namespace std;
 
void move(int n,char A,char B,char C)
 {
      if(n==1){
        cout<<A<<" ==> "<<C<<"\n";// nếu n = 1 thì dịch chuyển từ A -> C
      }
      else {        
        //// Nếu n > 1 thì thực hiện lần lượt các bước
        move(n - 1, A, C, B); // 1. Dịch chuyển n-1 đĩa từ A -> B
        cout<<A<<" ==> "<<C<<"\n"; //2. Dịch chuyển đĩa thứ n từ A -> C
        move(n - 1, B, A, C); // 3. Dịch chuyển n-1 đĩa từ B -> C
      }
 }
 
int main() {
  int n;
  cout<<endl<<"Nhập vào số đĩa N mà bạn muốn tìm cách giải: ";
  cin>>n;
  cout<<"Thứ tự dịch chuyển các vị trí A B C là: \n";
  move(n, 'A', 'B', 'C');
   
  cout<<"\n------------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Như vậy là chúng ta đã cùng nhau thực hiện chương trình sử dụng đệ quy để giải bài toán tháp Hà Nội trong C / C++. Cảm ơn các bạn rất nhiều, chúc các bạn thực hiện thành công !!!