【C语言】汉诺塔问题（递归）

一、汉诺塔问题

假设有a、b、c三根柱子，a柱子上从上到下、从小到大有n个圆盘，每次只能移动一个圆盘，移动过程中a、b、c三根柱子上都可以放圆盘，且必须是大盘在下、小盘在上，最终按照原有顺序将圆盘全部移动到c柱子上。

二、分析

假设有1个圆盘，如图所示，那么直接将圆盘移动到c柱子上即可。

假设有2个圆盘，如图所示，那么圆盘移动过程应是：a-->b,a-->c,b-->c。

假设有3个圆盘，如图所示，那么圆盘移动过程应是：a-->c,a-->b,c-->b,a-->c,b-->a,b-->c,a-->c。

假设有4个圆盘，如图所示，那么圆盘移动过程应是：a-->b,a-->c,b-->c,a-->b,c-->a,c-->b,a-->b,a-->c,b-->c,b-->a,c-->a,b-->c,a-->b,a-->c,b-->c。

 可以发现，当有n个圆盘时，可以先借助c柱子把较小的n-1个圆盘全都移动到b柱子上，再把a柱子上剩下的最大的一个圆盘移动到c柱子上。

这时候b柱子上有n-1个圆盘，需要再借助a柱子把剩下的n-1个圆盘移动到c柱子上，其实就相当于a柱子上有n-1个圆盘的情况。

这样就可以用递归的方法来求解。

三、程序实现

#include 

int count=0;

void Hanoi(int x,char a,char b,char c)
{
	count++;
    if(x==1)
		printf("%c-->%c\n",a,c);
	else
	{
	    Hanoi(--x,a,c,b);
		printf("%c-->%c\n",a,c);
		Hanoi(x,b,a,c);
	}
}

int main()
{
	char a='a';
	char b='b';
	char c='c';
    int num=0;
	printf("请输入圆盘数：");
	scanf("%d",&num);
	printf("步骤如下：\n");
	Hanoi(num,a,b,c);
	printf("共需移动%d步\n",count);
	return 0;
}

四、结果

 通过结果还可以看出，移动步数其实就是2^n-1。