小朋友学C语言（31）：递归解决汉诺塔
（一）汉诺塔介绍
汉诺塔（Hanoi Tower）问题是源于印度一个古老传说： 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。 n=64时，假如每秒钟移动一次，共需多长时间呢？ 2 ^ 64 - 1 = 18446744073709551615秒! 一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒。 这表明移完这些金片需要5845.54亿年以上。而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭！
（二）训练
在纸上画出n = 1, n = 2, n = 3, n = 4时的挪动步骤
（三）算法思想
将圆盘编号按从上到下的顺序表示为1，2，3……，n-1，n。 把所有的盘子分成两部分：上面的n-1个，第n个圆盘（即最下面的那个）。 （1）把上面的n-1个圆盘从柱子A移动到柱子B上，这一过程需要借助柱子C。 （2）把第n个圆盘从柱子A移动到柱子C上。这样第n个圆盘就放到了目标位置上。 （3）把上面的n-1个圆盘从柱子B移动到柱子C上，这一过程需要借助柱子A。
这里（1）用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。 同理（3）也用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。
（四）例子
例1：n = 2
要把两个盘子从A挪到C。分成三步：
（1）把上面那个盘子从A挪到B，需要1步
（2）把下面那个盘子从A挪到C，需要1步
（3）把上面那个盘子从B挪到C，需要1步
这样，两个盘子都从A挪到C上面了，任务完成！共需要1 + 1 + 1 = 3步。例2：n =3
要把三个盘子从A挪到C。分成三大步：
（1）把上面两个盘子从A挪到B，需要3步
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面两个盘子从B挪到C，需要3步
这样，三个盘子都从A挪到C上面了，任务完成！共需要3 + 1 + 3 = 7步。例3：n = 4
要把四个盘子从A都挪到C。分成三大步：
（1）把上面三个盘子从A挪到B，需要7步（具体可分为３步+1步+3步；3步又可以分为1步+1步+１步，这就是递归）
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面三个盘子从B移到C，需要7步
这样，四个盘子都挪到C上面了，任务完成！共需要7 + 1 + 7 = 15步。例4：n = 5
要把五个盘子从A都挪到C。分成三大步：
（1）把上面四个盘子从A挪到B，需要15步
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面四个盘子从B移到C，需要15步
这样，五个盘子都挪到C上面了，任务完成！共需要15 + 1 + 15 = 31步。（五）C语言实现
#include <stdio.h>
void hanoi(int n, char pillar1, char pillar2, char pillar3); // 函数声明
void move(int n, char pillar_from, char pillar_to); // 函数声明
int count; // 全局变量
int main()
{
int n;
// 输入汉诺塔层数（即金片数量）
printf("Please input the layer number of Hanoi Tower: ");
scanf("%d",&n);
// 目的：借助于B，把n个金片从A移动到C
hanoi(n, 'A', 'B', 'C');
return 0;
}
void hanoi(int n, char pillar1, char pillar2, char pillar3)
{
// 递归终止条件
if (n == 1)
{
move(n, pillar1, pillar3);
}
else
{
// 借助于pillar3，把上面的n-1个金片从pillar1移动到pillar2
hanoi(n - 1, pillar1, pillar3, pillar2);
// 把最下面的第n个金片从pillar1移动到pillar3
move(n, pillar1, pillar3);
// 借助于pillar1，把上面的n-1个金片从pillar2移动到pillar3
hanoi(n - 1, pillar2, pillar1, pillar3);
}
}
void move(int n, char pillar_from, char pillar_to)
{
count++; // 统计移动次数
printf("step %d: move layer %d, %c --> %c\n", count, n, pillar_from, pillar_to);
}运行结果：
Please input the layer number of Hanoi Tower: 1
step 1: move layer 1, A-->C
Please input the layer number of Hanoi Tower: 2
step 1: move layer 1, A-->B
step 2: move layer 2, A-->C
step 3: move layer 1, B-->C
Please input the layer number of Hanoi Tower: 3
step 1: move layer 1, A-->C
step 2: move layer 2, A-->B
step 3: move layer 1, C-->B
step 4: move layer 3, A-->C
step 5: move layer 1, B-->A
step 6: move layer 2, B-->C
step 7: move layer 1, A-->C说明：include的下面两行，分别是两个函数的声明。 为什么需要函数声明呢？因为编译器读取程序的时候，是从上到下读的，在main()函数中调用了这两个函数。但是编译器在调用的时候还不知道这两个函数是在哪里定义的。所以需要在main()函数的上方进行声明，告诉编译器“有这个东西，稍后会给出定义”。就是提前打招呼的意思。 以前那些课程，为什么都不需要函数声明呢？那是因为以前的所有程序，都把被调用的函数写到了main()函数的上方。编译器先读取被调用的函数，再读取main()函数，调用时已经知道之前有定义过，所以就不需要先声明了。
（六）作业
1 输入n = 3，进行调试 2 默写程序
腾讯云开发者
