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

Bài tập C: Giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy

Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội (Tower of Hanoi), mình xin nhắc lại một số qui tắc của trò chơi toán Tháp Hà Nội này:

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.

Phần dưới đây mình trình bày hai cách giải: sử dụng đệ quy và KHÔNG sử dụng đệ quy trong C.

Chương trình C: sử dụng đệ quy

Dưới đây là chương trình C để giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C trong C:

#include<stdio.h>

void TOH(int num, char x, char y, char z);

int main() {
   int num;
   printf("\nNhap so dia:");
   scanf("%d", &num);

   TOH(num - 1, 'A', 'B', 'C');
   return (0);
}

void TOH(int num, char x, char y, char z) {
   if (num > 0) {
      TOH(num - 1, x, z, y);
      printf("\n%c -> %c", x, y);
      TOH(num - 1, z, y, x);
   }
}

Biên dịch chương trình C trên sẽ cho kết quả:

Chương trình C: Không sử dụng đệ quy

#include <stdio.h>
#include <stdbool.h>

#define MAX 10

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){
   int i;
   printf("[");
	
   // Duyet qua moi phan tu 
   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }
	
   printf("]\n");
}

void bubbleSort() {
   int temp;
   int i,j;
   bool swapped = false;       
   
   // lap qua moi so 
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;
		
      // vong lap thu hai 
      for(j = 0; j < MAX-1-i; j++) {
         printf("Cap phan tu duoc so sanh: [ %d, %d ] ", list[j],list[j+1]);

         // Kiem tra: neu so tiep theo la nho hon so hien tai thi
         //   khong can trao doi vi tri cac so 
         //  (Muc dich: Noi bot (Bubble) cac so lon nhat) 
			
         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = true;
            printf(" => Trao doi vi tri [%d, %d]\n",list[j],list[j+1]);
         }else {
            printf(" => Khong trao doi\n");
         }
      }

      // Neu khong can trao doi cac so nua tuc la 
      //   mang da duoc sap xep. Thoat khoi vong lap 
      if(!swapped) {
         break;
      }
      
      printf("Vong lap thu %d#: ",(i+1)); 
      display();                     
   }    
}


main(){
   printf("Mang du lieu dau vao: ");
   display();
   printf("\n");
   bubbleSort();
   printf("\nMang sau khi da duoc sap xep: ");
   display();
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Các bạn có thể mua thêm khóa học JAVA CORE ONLINE VÀ ỨNG DỤNG cực hay, giúp các bạn vượt qua các dự án trên trường và đi thực tập doanh nghiệp với Java. Khóa học có giá chỉ 400K, nhằm ưu đãi, tạo điều kiện cho sinh viên cho thể mua khóa học.

Nội dung khóa học gồm 16 chuơng và 100 video cực hay, học trực tiếp tại https://www.udemy.com/tu-tin-di-lam-voi-kien-thuc-ve-java-core-toan-tap/ Bạn nào có nhu cầu mua, inbox trực tiếp chị Thu, trợ lý anh Tuyền để hỗ trợ thanh toán qua mã QR ngân hàng Việt Nam, fb: https://www.facebook.com/Thule.59

Anh Tuyền, tác giả khóa học, là cựu sinh viên chương trình đào tạo kĩ sư tài năng của đại học Bách Khoa Hà Nội với hơn 5 năm kinh nghiệm đi làm thực tế doanh nghiệp và cũng là Founder website vietjack.com, web giáo dục phổ biến nhất Việt Nam hiện tại (năm 2024). Java cũng là ngôn ngữ lập trình dễ đi xin việc nhất hiện tại, với mức lương cao, hãy nâng cao kiến thức IT của bản thân mình vì một Việt Nam giàu mạnh.

Loạt bài hướng dẫn của chúng tôi dựa một phần trên nguồn tài liệu của: Tutorialspoint.com