这几天在家看完了《》这本书，里面的内容深入浅出比较容易理解，将一个个晦涩的数学概念用经典例题讲解，使人不觉得枯燥。这本书看第一遍有两处地方卡壳，不是很懂，再看第二遍大致能捋清了，其中一个就是我这篇文章要讲的经典。
汉诺塔是一个由数学家（Edward Lucas）于1883年发明的游戏，该游戏中包含了三根细柱（A、B、C），A柱上套有6个圆盘，这些圆盘大小各异，按从大到小的顺序自下而上摆放，如图1所示：
现在要把套在A柱子上的6个圆盘全部转移到B柱上，并且在移动圆盘时必须遵守以下规则：
一次只能移动柱子最上端的一个圆盘
小圆盘上不能放大圆盘
将一个圆盘从一根柱子移到另一根柱子，算移动“1次”，那么，将6个圆盘全部从A移到B最少需要移动几次呢?
分析思路：我们先考虑小的汉诺塔，并找出其中的规律。首先，我们假设将n个圆盘从A移到B最少需要f(n)次。
当n = 0时，我们不需要移动， f(0) = 0；
当n = 1时，f(1)即将1个圆盘从A移到B，我们可以直接移动过去，所以f(1) = 1；
当n = 2时，我们要先把第一个圆盘从A柱移到C柱，再将第二个圆盘从A柱移到B柱，最后再将C柱上的圆盘移到B柱，总共移动了三次，所以f(2) = 3；
当n = 3时，第一步我们先将A上面的两个圆盘移动到C，这个过程就相当于f(2)的过程，只是f(2)的中间柱是C，而这一过程的中间柱是B，总的来说，中间柱就是除了始发柱和目标柱以外的那根柱子，作用是用来暂时放置那些小圆盘的；第二步将最下面那个圆盘移到B；最后一步将C上的两个圆盘移到B，和第一步类似。这整个过程其实就是先实施一个
f(n - 1)的方案，将起始柱上面的那（n - 1）个圆盘移动到中间柱上，再将最底层的那个圆盘移动到目标柱上，最后再实施一个f(n - 1)的方案，将中间柱上的那（n - 1）个圆盘一个个移到目标柱上。因此f(3) = f(2) + 1 + f(2) = 7。
这就是一种递归，f(n) = 2f(n - 1) + 1 = 2**n - 1，所以要把套在A柱子上的6个圆盘全部转移到B柱，需要f(6)次，f(6) = 2**6 - 1 = 63。具体的移动方案还应该加入几个参数，即起始柱x、中间柱y、目标柱z，函数设为hanoi(n, x, y, z)，具体实施代码如下：
#include#include void hanoi(int n, char x, char y, char z);void hanoi(int n, char x, char y, char z) { if(n == 0) {} else { /*调用第（n - 1）层函数，也是第一步，将（n - 1）个圆盘移到中间柱y上。 这一过程中，目标柱就是y，所以n - 1层函数里参数换了位置。*/ hanoi(n - 1, x, z, y)； /*将剩下的那个圆盘移到目标柱z。*/ printf("%c to %c,", x, z)； /*将中间柱y上的那（n - 1）个圆盘移到目标柱z，这里又要调用（n - 1） 层函数。*/ hanoi(n - 1, y, x, z); } } int main(void) { hanoi(6, 'A', 'B', 'C'); system('pause'); return EXIT_SUCCESS; }
运行一下吧，看看你得到的结果。