下载掌阅APP，畅读海量书库
立即打开
汉诺塔问题是心理学实验研究常用的任务之一，在医学临床上也常将汉诺塔任务用于测查脑损伤者的执行功能。汉诺塔问题主要涉及三根高度相同的柱子和大小互不相同的一套64个圆盘，3根柱子分别用起始柱A、辅助柱B及目标柱C代表。汉诺塔问题的目标是通过辅助柱B，将64个圆盘从起始柱A移动到目标柱C上。移动过程中，每次只能移动一个盘子，所有柱子上的盘子必须小盘在上、大盘在下。
假设初始时盘子依序放在A柱上，盘子由1开始从上向下编号，先对问题进行必要分析获得问题的通解。
（1） n =1时，只有一个盘子，问题可直接解决。
（2） n =2时，2个盘子需要借助其他柱子才能完成。
（3） n =3时，移动次数明显增多。
（4） n =4时，移动次数为15。
……
以此类推，得到各项对应的形式为： F 1 =1， F 2 =3， F 3 =7，…， F n =2 F n -1 +1=2 n -1，当 n =64时， F 64 =2 64 -1=18446744073709551615，即使移动一次用一秒，移动完成也要5000多亿年。
要想理解递归算法解决汉诺塔问题，关键在于得“麻痹”自己，相信自己像神笔马良一样会使用“神笔”，从整体上看待整个问题的解决过程，通过抽象将局部细节先暂存于假设之中，从而可以将问题分为3个大的步骤来解决，如图3-1所示。
（1）将A柱顶端的 n -1个盘子通过施展“神笔”借助C柱移动到B柱上，此时A柱只剩最大1个盘子，B柱有 n -1个盘子，C柱为空。
（2）第二步非常简单，直接将最大的盘子从A柱移动到C柱。
（3）将B柱上的 n -1个盘子再次施展“神笔”，借助A柱移动到C柱上，至此大功告成！
图3-1 汉诺塔问题解题3步示意图
在此过程中，始终让人耿耿于怀的莫过于“神笔”功能是如何施展的。这个“神笔”的施展正是递归的精华所在。两次施展“神笔”处理的盘子数目都是 n -1个，规模小于原始问题的规模，求解方法却与原始问题相同。所以，“神笔”的施展与 n 个盘子时的处理方法相同，只需将图3-1中的 n 变为 n -1即可。处理 n -1个盘子时，可令 m = n -1，问题（1）就变成了将 m 个盘子从A柱借助C柱移动到B柱的过程，问题（3）则是将 m 个盘子从B柱借助A柱移动到C柱的过程。对于 m 个盘子的处理，与 n 个盘子处理的流程完全一致，这样一直递推下去，直至一个盘子时结束。
求解汉诺塔问题的主体功能的是hano（）函数，main（）函数用于测试，move_dishes（）函数用于输出移动圆盘的提示信息。
move_dishes（）函数的主要功能是输出实际移动圆盘时的提示信息，同时统计移动圆盘的总次数。因为函数执行后需要将总移动次数返回到hano（）函数供下次计数使用，所以代表移动次数的count变量必须为指针变量。
hano（）函数包括有5个参数， n 为圆盘的个数，A为起始柱对应的标识字母，B为辅助柱对应的标识字母，C为目标柱对应的标识字母，指针count用于统计移动次数。当只有一个圆盘时，直接将圆盘从A柱移动到C柱；当圆盘数多于一个时，需要施展“神笔”进行“三步走”，先将 n -1个圆盘从A柱借助C柱移动到B柱，然后将最大圆盘从A柱移动到C柱，最后将 n -1个圆盘从B柱借助A柱移动到C柱。
实现代码如下。
当圆盘个数为3时，运行结果如下。
