BT10: Sử dụng đệ quy giải quyết bài toán tháp Hà Nội
1. Yêu cầu
Viết chương trình C# sử dụng hàm đệ quy để giải bài toán Tháp Hà Nội. Bài toán tháp Hà Nội (Tower of Hà Nội) là một trò chơi toán học gồm 3 cột và số đĩa nhiều hơn 1. 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.
2. Thuật toán
Qui ước: Đặt tên 3 cột là A B C để tiện theo dõi. Yêu cầu bài toán là chuyển n chiếc đĩa từ cột A sang cột C.
Cách giải:
Đầu tiên ta lấy cột C làm cọc trung gian. Chuyển n-1 chiếc đĩa sang cột B.
Ta chuyển chiếc đĩa lớn nhất sang cột C
Lấy cột A làm cột trung gian chuyển n-1 chiếc đĩa từ cột B sang cột C
Hình ảnh dưới đây miêu tả cách giải này:
//Hàm tower di chuyển n đĩa, từ cọc nào tới cọc nào và một cọc trung gian
void towers(int n, char from, char to, char aux)
{
//Điểm dừng của hàm đệ quy khi chỉ còn 1 đĩa, di chuyển từ cọc tới cọc
if(n==1)
{
printf("Di chuyển đĩa 1 từ %c tới %c\n",from,to);
return;
}
else
{
//Gọi hàm đệ quy di chuyển n-1 đĩa tới cọc phụ
towers(n-1,from,aux,to);
printf("Di chuyển đĩa %d từ %c tới %c\n",n,from,to);
//Gọi hàm đệ quy di chuyển n-1 đĩa từ cọc phụ về cọc ban đầu
towers(n-1,aux,to,from);
}
}