[one_demo_10]递归解决汉诺塔问题
有3个座a、b、c，开始时在a座上有64个盘子，盘子大小不等，大的在下，小的在上。把64个盘子从a座移动到c座，规定每次只允许移动一个盘子，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用b座。编程实现移动盘子的步骤。
分析，如果只有1个盘子，是移动一次；如果是2个盘子，移动3次；如果是3个盘子，是移动7步。推测，移动的公式是2的n次方-1。
递推移动的机制，将移动n个盘子看成是移动第n个和n-1个，那么，将n-1看成是一个整体，相当于移动2个盘子，从示意图中可以看出移动n个盘子将相当于将n-1个从a移动到b的次数加上从b移动到c的次数再加上第n个移动的1次，相当于前n-1个盘子整体移动了两次，而在这种从一个底座移动到另一个底座的最短算法是一样多的，也就是前n-1个盘子两次移动到c，算术表示就是2*（n-1移动到c的次数），总体上移动n个盘子，也就是相当于：2*（前n-1个盘子移动到c盘的次数）+1。n和n-1这个整体移动到c示意如
a b c
n-1
开始时 n
第1次移动 n n-1
第2次移动 n-1 n
n-1
第3次移动 n
那么，将n个盘子移动到c的结果就是2*（n-1个的移动到c的次数）+1，如此类推形成递归。递归结束的条件是n=1时为1。当n=2时为3，注意n=2时的情况也满足这个公式，所以以n=1为递归结束条件。从简单的数验证就是，比如n=3时，总次数等于到2*3+1等于7。
起始 a b c
kai 1
ss 2
起始 3
ss
ss 2
ss 3 1
第1次
ss
ss 3 2 1
第2次
ss 1
第3次 3 2 （此时已经将前2个作为整体移动到了b，也相当于移动到c的次数，也就是移动了3次）
ss 1
第4次 2 3 （这一次是将3移动到目标位置）
ss
第5次 1 2 3 （接下来就是将前2个移动到c，也是3次）
ss 2
第6次 1 3
ss 1
ss 2
第7次 3
那么模拟移动的步骤，根据示意图
a b c
n-1
开始时 n
第1次移动 n n-1
第2次移动 n-1 n
n-1
第3次移动 n
如果n大于1时，实际上是先移动n-1从a到b，再移动n到c，再移动n-1从b到c。
那么，编程实现
int hannuota(int a)
{
if (a == 1)
{
return 1;
}
else
{
return 2 * hannuota(a - 1) +1;
}
}
//设计递归函数，实现模拟移动的步骤
void hannuotazoufa(chara, char b, char c, int num)
{
if (num == 1)
{
printf("%c->%c\n",a, c);
}
else
{
hannuotazoufa(a, c, b, num -1);
printf("%c->%c\n",a, c);
hannuotazoufa(b, a, c, num -1);
}
}
void main()
{
int panzi = 4;
printf("请输入汉诺塔的盘子\n");
scanf("%d", &panzi);
int res = hannuota(panzi);
printf("%d个盘子的汉诺塔移动次数为%d\n", panzi, res);
printf("移动的方式为\n");
hannuotazoufa('a', 'b', 'c', panzi);
system("pause");
}