汉诺塔代码图文详解(递归入门)

游戏规则：

首先我们模拟(N=2，3，4).

这是两层汉诺塔的移动步骤.

这是三层汉诺塔的步骤.

这是四层的汉诺塔步骤.

移动规律:做完模拟之后可以很自然地发现,要把N层的汉诺塔从A柱移至C柱,首先是要把上面(N-1)片圆盘全部拿掉（也就是移至B处）,然后才能把 第 N片圆盘移至C柱．
当我们成功地把第N片圆盘移至C柱时，问题转化成了要把B柱上的(N-1)片圆盘移至C处.然后重复上述操作:把(N-2)片圆盘全部移至A柱,再把 第 (N-1)片圆盘移至C柱…
思路分析:从移动规律上看,我们是把要移动的n片圆盘分成两个整体:(n-1)片和第n片,那么这两个整体可以看作是N=2的汉诺塔问题的部分解.

关于移动次数的分析:观察上述过程图,发现中间部分的关于"n-1"层的移动实际上是不进行的,它其实是我们分析问题的中间假象项,它由下一层递归去实现,而下一层的"n-1"层的移动又是由下一层递归去实现,最后递归到"n-1"=1时,这一次的"n-1"项才真正开始移动.那么,每下一次递归的关于"n-1"层的移动项是这一次关于"n-1"的移动项的2倍.所以当n-1次递归后,最后会造就 2^(n-1) ①次数的"n-1"=1的移动…
而关于第n层移动的项每次递归都会执行一次.那么关于第n层移动的次数是2⁰ + 2¹ +2² +2³ +…+ 2^n-2 ②;
综合①②得Sn=2⁰ + 2¹ +2² +2³ +…+ 2^n-2+2^n-1 ;
Sn是关于a1=1,an=2^n-1的等比数列.
计算得Sn=2ⁿ -1

[结合上述内容其实不难发现,我们可以用递归的思想去实现代码]

如果还不是很清楚,我们不妨先打下代码的大致框架，随后逐步完善。。。

//代码框架
#include<stdio.h>
void Move()	
{
}
void HannuoTower()
{
}
int main()	
{
	int N;
	scanf("%d",&N);
	HannuoTower();
}

由模拟(N=2,3,4)的过程图得知,HannuoTower函数分为三个步骤:
(A柱B柱C柱视不同情况而分为:圆盘当前所在位置,要移动的目标位置,临时存放的第三位置)
1.先移动(n-1)片圆盘到第三位置 //(无法一次性实现)这个步骤的实现用递归
2.再移动 第 n片圆盘到目标位置 //Move函数直接移动输出
3.最后移动(n-1)片圆盘到 第 n片圆盘之上(也就是目标位置) //实现方法同步骤1.

于是乎,HannuoTower函数和Move可以写成如下形式

void Move(char a,char c)
{
	printf("%c -> %c",a,c);
}
void HannuoTower(void n,char a,char b,char c)//n为层数
//固定地将形参a视为当前位置,形参b视为临时位置,形参c视为目标位置.
{
	HannuoTower(n-1,a,c,b); //较下一次情况,临时位置和目标位置的身份互换
	Move(a,c);//输出 当前位置移至目标位置的信息
	HannuoTower(n-1,b,a,c);//较下一次情况,当前位置和临时位置的身份互换
}

这里要注意一点的是,此时的HannuoTower函数是无法作用的,当n减到1时,它还是会递归下去.递归函数最重要的是设置出口,这里我们可以用if语句去判断跳出的条件(n==1).
此外,为了方便观察汉诺塔游戏的过程和研究圆盘移动次数的计算规律.我们可以另加一个全局变量count,用来计数移动的次数.

补充完整的代码如下.

#include<stdio.h>
int count=1;
void Move(char a,char c)
{
	printf("第%d次,%c -> %c\n",count,a,c);
	count++;
}
void HannuoTower(int n,char a,char b,char c)
{
	if(n==1)Move(a,c);
	else
	{
		HannuoTower(n-1,a,c,b);
		Move(a,c);
		HannuoTower(n-1,b,a,c);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	HannuoTower(n,'A','B','C');
}