Lập trình .NET

Lập trình .NET

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.
Bài toán tháp hà nội


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:
Thuật giải bài toán tháp hà nội


//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);
         }
}


3. Video hướng dẫn

4. Code

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Share via
Copy link
Powered by Social Snap