汉诺塔问题的c语言递归

汉诺塔问题的c语言递归 汉诺塔问题的c语言递归

C语言递归程序代码如下：

#include
int c=0;
void move(char x,int n,char z)
{
	printf("第%i步：将%i号盘从%c->%cn",++c,n,x,z);
}
void hanoi(int n,char x,char y,char z)
{
	if(n==1)
		move(x,1,z);
	else
	{
		hanoi(n-1,x,z,y);
		move(x,n,z);
		hanoi(n-1,y,x,z);
	}
}
void main()
{
	int n;
	while(printf("3个塔座为a、b、c，圆盘最初在a座，借助b座移到c座。请输入圆盘数：")!=EOF){
	scanf("%d",&n);
	hanoi(n,'a','b','c');	
	}
}

n层汉诺塔的移动步骤可以看成以下三步(汉诺塔从n到1逐渐减小):

1.n上面的n-1个汉诺塔移动到第三个柱子

2.n号汉诺塔移动到第二个柱子

3.将第二个柱子上的n-1个汉诺塔移动到第三个柱子

这样第1和第3所用的时间是相同的

四层汉诺塔的移动步骤如下图所示

仔细观察会发现第7步和第8步第四层汉诺塔的位置是相反的。

同样的在第6步和第9步中第一、四层的位置也是相反的。

那不难理解，在n层汉诺塔中，当第n层汉诺塔到达第三个柱子时，之后经历的步骤和将第n层汉诺塔从第一个柱子移动到第三个柱子的步骤是相对的(相对不是相反，相反只是指位置)

所以对于程序的实现，来读一读源代码。举例：n=1和n=2时程序的步骤

第一步

从main函数开始输入n(即代表n层汉诺塔)，然后调用void hanoi(int n,char x,char y,char z)函数，输入n和a、b、c三个柱子。

跳转到hanoi函数进行判断

如果n=1，则直接调用move函数将第一层汉诺塔移动到c柱即可。

但当n>1时，则进入递归。

当n=2时，hanoi函数输入的参数如下hanoi(2-1,a,c,b);

第二步

再次进入hanoi，这时n=1，则将进行第一步，跳转进move函数，将第一层汉诺塔直接送到第三个柱子，即b柱。

程序跳回n=2时hanoi程序，这时执行move(a,2,c),即将第二层汉诺塔移动到c柱。

第三步

再次跳回到n=2时的hanoi程序，这次执行到了第二个hanoi函数，这时变成了hanoi(2-1,b,a,c)，即第二层汉诺塔从b柱移动到了c柱。

将问题化为整体来看，当有n层汉诺塔时，程序运行步骤如下：

第一步：

将n-1层汉诺塔从a柱移动到b柱

第二步：

将第n层汉诺塔移动到c柱

第三步：

将n-1层汉诺塔从b柱移动到c柱