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é. Show 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:
Ý tưởng giải bài toán tháp Hà Nội bằng đệ quyQuy 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:
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) { }Giải thích:
Giả sử mình có n = 3 (số đĩa bằng 3) thì số lần thực hiện bằng 23 - 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) { }
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) { }
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 !!! |