Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội (Tower of Hanoi), hãy cùng nhau xem lại một số qui tắc của trò chơ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 thú vị, bao gồm 3 cột và một số đĩa nhiều hơn 1. Hình minh họa bên dưới là trường hợp có 3 đĩa.
Các đĩa có kích cỡ khác nhau và được xếp theo thứ tự tăng dần từ trên xuống, tức là đĩa nhỏ hơn sẽ nằm trên đĩa lớn hơn. Với số đĩa khác nhau, ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, nhưng lời giải cho chúng đều tương tự. 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ột. Với số cột lớn hơn, việc tìm lời giải cho bài toán vẫn đang trong quá trình nghiên cứu.
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 từ cột này sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa, tức là đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi Tháp Hà Nội (Tower of Hanoi):
- Chỉ được di chuyển một đĩa từ cột này sang cột khác trong mỗi lần di chuyển.
- Chỉ được di chuyển đĩa nằm trên cùng của cột (không được di chuyển các đĩa ở giữa).
- Đĩa có kích thước lớn hơn không thể được đặt lên đĩa có kích thước nhỏ hơn.
Dưới đây là một hình minh họa cho 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 n được giải trong ít nhất 2^n - 1 bước. Vì vậy, 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 2^3 - 1 = 7 bước.
Phần tiếp theo sẽ trình bày hai cách giải bài toán Tháp Hà Nội (Tower of Hanoi): sử dụng đệ quy và không sử dụng đệ quy trong ngôn ngữ lập trình 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 ngôn ngữ C:
#include<stdio.h>
void TOH(int num, char x, char y, char z);
int main() {
int num;
printf("Nhập số đĩa:");
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 và chạy chương trình C trên sẽ cho kết quả như sau:
Nhập số đĩa: 3
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> BChương trình C: Không sử dụng đệ quy
Dưới đây là chương trình C không sử dụng đệ quy để giải bài toán Tháp Hà Nội (Tower of Hanoi) trong ngôn ngữ C:
#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("[");
for (i = 0; i < MAX; i++) {
printf("%d ",list[i]);
}
printf("]\n");
}
void bubbleSort() {
int temp;
int i, j;
bool swapped = false;
for (i = 0; i < MAX-1; i++) {
swapped = false;
for (j = 0; j < MAX-1-i; j++) {
printf("Cặp phần tử được so sánh: [ %d, %d ] ", list[j],list[j+1]);
if (list[j] > list[j+1]) {
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
swapped = true;
printf(" => Trao đổi vị trí [ %d, %d ]\n",list[j],list[j+1]);
} else {
printf(" => Không cần trao đổi\n");
}
}
if (!swapped) {
break;
}
printf("Vòng lặp thứ %d#: ",(i+1));
display();
}
}
int main() {
printf("Mảng dữ liệu đầu vào: ");
display();
printf("\n");
bubbleSort();
printf("\nMảng sau khi đã được sắp xếp: ");
display();
return 0;
}Kết quả chạy chương trình C trên sẽ được hiển thị như sau:
Mảng dữ liệu đầu vào: [1 8 4 6 0 3 5 2 7 9]
Cặp phần tử được so sánh: [1, 8] => Không cần trao đổi
Cặp phần tử được so sánh: [8, 4] => Trao đổi vị trí [ 4, 8 ]
Cặp phần tử được so sánh: [8, 6] => Trao đổi vị trí [ 6, 8 ]
Cặp phần tử được so sánh: [8, 0] => Trao đổi vị trí [ 0, 8 ]
Cặp phần tử được so sánh: [8, 3] => Trao đổi vị trí [ 3, 8 ]
Cặp phần tử được so sánh: [8, 5] => Không cần trao đổi
Cặp phần tử được so sánh: [8, 2] => Trao đổi vị trí [ 2, 8 ]
Cặp phần tử được so sánh: [8, 7] => Trao đổi vị trí [ 7, 8 ]
Cặp phần tử được so sánh: [8, 9] => Không cần trao đổi
Vòng lặp thứ 1#: [1 4 6 0 3 5 2 7 8 9]
Cặp phần tử được so sánh: [1, 4] => Không cần trao đổi
Cặp phần tử được so sánh: [4, 6] => Không cần trao đổi
Cặp phần tử được so sánh: [6, 0] => Trao đổi vị trí [ 0, 6 ]
Cặp phần tử được so sánh: [6, 3] => Trao đổi vị trí [ 3, 6 ]
Cặp phần tử được so sánh: [6, 5] => Không cần trao đổi
Cặp phần tử được so sánh: [6, 2] => Trao đổi vị trí [ 2, 6 ]
Cặp phần tử được so sánh: [6, 7] => Không cần trao đổi
Vòng lặp thứ 2#: [1 4 0 3 5 2 6 7 8 9]
Cặp phần tử được so sánh: [1, 4] => Không cần trao đổi
Cặp phần tử được so sánh: [4, 0] => Trao đổi vị trí [ 0, 4 ]
Cặp phần tử được so sánh: [4, 3] => Trao đổi vị trí [ 3, 4 ]
Cặp phần tử được so sánh: [4, 5] => Không cần trao đổi
Cặp phần tử được so sánh: [4, 2] => Trao đổi vị trí [ 2, 4 ]
Cặp phần tử được so sánh: [4, 6] => Không cần trao đổi
Vòng lặp thứ 3#: [1 0 3 4 2 5 6 7 8 9]
Cặp phần tử được so sánh: [1, 0] => Trao đổi vị trí [ 0, 1 ]
Cặp phần tử được so sánh: [1, 3] => Không cần trao đổi
Cặp phần tử được so sánh: [3, 4] => Không cần trao đổi
Cặp phần tử được so sánh: [4, 2] => Trao đổi vị trí [ 2, 4 ]
Cặp phần tử được so sánh: [4, 5] => Không cần trao đổi
Vòng lặp thứ 4#: [0 1 3 2 4 5 6 7 8 9]
Cặp phần tử được so sánh: [0, 1] => Không cần trao đổi
Cặp phần tử được so sánh: [1, 3] => Không cần trao đổi
Cặp phần tử được so sánh: [3, 2] => Trao đổi vị trí [ 2, 3 ]
Cặp phần tử được so sánh: [3, 4] => Không cần trao đổi
Vòng lặp thứ 5#: [0 1 2 3 4 5 6 7 8 9]
Cặp phần tử được so sánh: [0, 1] => Không cần trao đổi
Cặp phần tử được so sánh: [1, 2] => Không cần trao đổi
Cặp phần tử được so sánh: [2, 3] => Không cần trao đổi
Vòng lặp thứ 6#: [0 1 2 3 4 5 6 7 8 9]
Cặp phần tử được so sánh: [0, 1] => Không cần trao đổi
Cặp phần tử được so sánh: [1, 2] => Không cần trao đổi
Vòng lặp thứ 7#: [0 1 2 3 4 5 6 7 8 9]
Mảng sau khi đã được sắp xếp: [0 1 2 3 4 5 6 7 8 9]Nên nhớ rằng các chương trình trên chỉ mang tính minh họa và thực hiện trên một số dữ liệu đầu vào cố định. Bạn có thể tùy chỉnh các giá trị trong chương trình để thử nghiệm kết quả với dữ liệu khác nhau.
Hy vọng rằng bài viết này đã giúp bạn hiểu rõ hơn về bài toán Tháp Hà Nội (Tower of Hanoi) và cách giải quyết nó sử dụng đệ quy trong ngôn ngữ lập trình C.