听郝斌老师_汉诺塔（河内塔）分析

首先，把汉诺塔的问题写下来：

由三根固定的柱子ABC和不同尺寸的n个圆盘组成.开始时,这些个大小不同的圆盘依其半径大小依次套在A柱上,使大圆盘在底下。

游戏的规则是:每次的圆盘从一根柱子移到另一根柱子上,但是不允许这个圆盘放在比它小的圆盘上面。

游戏的目标是：把所有的圆盘从按照大小的次序从A柱都移到C根柱子上,可以利用中间的B柱子,在移动过程中要始终将最大的圆盘放在最下面。

声明：盘子从小到大依次编号：1,2,3...n。

如下图：

总之，我们现在要解决的问题就是：将A柱子上的盘子借助 B柱子全部挪到C柱子上，在这个过程中，小盘子永远只能在大盘子上。（借助一词用的很精妙，慢慢体会）

解决这个问题先将伪代码的思路写下来：

if（n>1）

{
如果：是1个盘子
直接将A的盘子从A移到C
否则：
A的n-1个盘子从A借助C移到B
A的第n个盘子直接从A移到C
B的n-1个盘子借助A移到C
}

该思路使用递归方式解决问题，递归的精髓我还是没有掌握，总感觉少些什么，每次做题都是自己想不到怎样使用递归，但是看了解决题目的代码之后就有种恍然大悟的感觉，希望有掌握递归的朋友可以留言，解决我的困惑，非常感谢！

汉诺塔代码如下：

 1 /*
 2   伪算法：
 3 if（n>1）{
 4 如果：是1个盘子
 5     直接将A的盘子从A移到C
 6 否则：
 7     A的n-1个盘子从A借助C移到B
 8         A的第n个盘子直接从A移到C
 9         B的n-1个盘子借助A移到C
10 }
11 */
12 #include <stdio.h>
13 
14 int m = 0;
15 
16 void HanNuoTa(int n, char A,char B, char C)
17 {
18     if(1 == n)
19     {
20         printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);
21         ++m;
22     }
23     else
24     {
25         HanNuoTa(n-1, A, C, B);
26         printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);
27         ++m;
28         HanNuoTa(n-1, B, A, C);
29     }
30 }
31 int main(void)
32 {
33     char A = 'A';
34     char B = 'B';
35     char C = 'C';
36     int n;
37 
38     printf("请输入要移动盘子的个数：");
39     scanf("%d", &n);
40 
41     HanNuoTa(n, A, B, C);
42     printf("一共挪动 %d 次
", m);
43 
44     return 0;
45  }

上面的代码没有注释，因为我不知道该怎样下手，下面听我分析：

先来看一看汉诺塔在数学中的求解过程，

从这里开始：

令Hn表示解n个圆盘的汉诺塔游戏所需要的移动次数,建立关于序列{Hn}递推关系

解：

1. 开始时n个圆盘在A柱上,按照游戏规则用次移动，将上面的n-1个圆盘移到B柱子上,在这些移动中最大圆盘不动。

2.然后,用1次移动将最大圆盘移到C柱子上.

3.再用次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

于是,得到所求递推关系：

其中，初始条件因为根据游戏规则,一个圆盘可用1次移动从A柱子放到C柱子上（这句话很重要）。

上面的解题思路要看懂，仔细品味一下。

为求解上述递推关系,对该问题首先用构造方法导出其解公式如下:

这个公式很复杂，我没有看懂（原谅我数学没有学好），有会的朋友可以推导一下增长数学知识。但是，重点不是这个，公式没看懂没有关系，继续向下看。

那么，我们可以得出结论：n个盘子总共需要移动的次数为。

答案有了，代码有了并且能够运行正确。好，我们的问题解决了。

有的朋友到了这一步可能会觉得大功告成就不管了，反正要用到的时候复制一下代码就好。那么朋友你可以去做别的事情了，下面我们讲的代码思路就和你没有关系了。

首先，汉诺塔使用递归方法是很容易写出代码的，但是盘子数不能过大，否则运行的结果会刷屏并且停不下来（不信你用64个盘子试试）。

那么递归要注意的是关键步骤，中间的过程我们是不用去关注的，那是计算机要做的事情。如果想要了解具体过程最好用盘子数为3或者4来体验。

什么是关键步骤？（递归的精髓就在这里，我只是掌握了一点，如果有朋友看下面的思路有感觉了，那么请你在继续努力一下。）

1.初始条件，我也称它为终止递归的条件。对于人类的思维来说就是第一步我们要做什么，但是对于计算机的递归来说就是递归到最后的结束条件。

其中，初始条件因为根据游戏规则,一个圆盘可用1次移动从A柱子放到C柱子上。上面的这句话还记得吗？

通过这句话我们得到了下面的代码：

1 if(1 == n)
2     {
3         printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);
4         ++m;
5     }

这就是在只有一个盘子的时候，我们要做的步骤，将1号盘子从A柱子移动到C柱子上。

这时候就会有个疑问，你怎么知道在移动的过程中A变量就是A柱子，C变量就是C柱子？万一A变量表示的是B柱子或C柱子怎么办？不是万一，是肯定在移动的过程中A变量代表的就是B柱子或者C柱子。有这个疑问说明你在思考，带着这个疑问看下面的分析

下面的代码将会解决你的问题：

1 else
2     {
3         HanNuoTa(n-1, A, C, B);
4         printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);
5         ++m;
6         HanNuoTa(n-1, B, A, C);
7     }

void HanNuoTa(int n, char A,char B, char C)

HanNuoTa(n - 1, A, C, B);//这句话的解析是

1. 开始时n个圆盘在A柱上,按照游戏规则用次移动，将上面的n-1个圆盘移到B柱子上,在这些移动中最大圆盘不动。（也就是将A柱子上的n-1个盘子，借助C柱子移动到B柱子上）。

对于我们人来说，要移动n个盘子的第一步是什么？两种选择：将1号盘子从A挪到B上，或者从A挪到C上。但是我们不确定到底怎样移动才是正确的做法。

这时候，递归的威力发挥出来了，我们不考虑第一步是什么，万一第一步走错了那么接下来再怎么移动都是白费力气。

好，我们换种思考方式，如果A柱子上面的n-1个盘子借助 C柱子全部移到了B柱子上面，移动次数为：

HanNuoTa(n-1, A, C, B);

2.然后,用1次移动将最大圆盘移到C柱子上.

 printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);

如上面第2步所述，我们要做的事情就是，把A上的第n个盘子移动到C柱子上：

3.再用次移动将B柱子上的n-1个圆盘移到C柱子上并且放到最大圆盘上面。

HanNuoTa(n-1, B, A, C);

同样，如第3步所述，再将B柱子上面的n-1个盘子借助 A柱子移动到C上：

就这样我们把n个盘子全部移动到了C上。

我们看第1步、第3步的函数，和HanNuoTa原函数对比：

void HanNuoTa(int n, char A,char B, char C)

     HanNuoTa(  n-1,      A,     C,      B);//第一步

     HanNuoTa(  n-1,      B,     A,      C);//第二步

     printf("将编号为%d的盘子直接从%c柱子移到%c柱子
", n, A, C);//输出目标永远是这句话，A->C，因为我们题目告诉我们把A柱子上的盘子全部移动到C上。

函数在调用自己的时候，A B C三者原来的值，在调用的时候就已经被替换了，其中，我们输出的目标始终是A->C，B柱子永远是被A借助的，所以在调用的时候

如第一步：A的n-1个盘子移动到B上，这时候A柱子上的n-1个盘子要移动，所以A = A；C柱子是被借助的，所以我们让B = C，目标是移动到B柱子上，所以要让C = B。这样就又符合我们的目标了A->C ，这时候的C已经是B了。

同理，第二步：B上的n-1个盘子移动到C上，根据输出目标A->C，我们让A = B，B = A，C = C；这时候的A->C其实等价于B->C。

对了，还有源代码中m变量是计算移动的次数的。

这时候A柱子的n个盘子全部移动到了C柱子上，但是还有一个问题没有解决好，就是第一步：A上的n-1个盘子是怎样移动到B柱子上的，还有第三步：B上的n-1个盘子是怎样移动到C柱子上的。如果想到了这个，说明你和我当时的问题是一样的，这个问题也正是困扰我的地方。

我当时听到的解答就是在重复上面的步骤，如上面第一步A上的n-1个盘子是怎样移动到B柱子上的可以这样解决：

1.将A上的n-2个盘子先移动到C上

2.然后，将A上的第n-1个盘子移动到B上

3.最后将C上的n-2个盘子移动到B上

完美解决，prefect。

可是我想的有点多，就是之前的A上的第n个盘子怎么办？

其实，认真思考一下，画张图就很好理解了：

1.将A上的n-2个盘子先移动到C上

2.然后，将A上的第n-1个盘子移动到B上

3.最后将C上的n-2个盘子移动到B上

因为，A上是第n个盘子，比前n-1个盘子都要大，所以C的n-2个盘子是可以借助A柱子全部移动到B上的。

接下来的步骤就是

把A上的第n个盘子移动到C上，就和上面讲的把n-1个盘子移动到C上一样了。

同理，第三步：B上的n-1个盘子是怎样移动到C柱子上的，也是与上面的类似的移动步骤。

这就是我们所说的当n个盘子的时候考虑n-1个怎样移动，n-1个考虑n-2个怎样移动，一直递推到n=1，这个时候计算机已经知道A变量和C变量具体代表的是哪根柱子了，于是它就会移动，当移动完成之后，就会返回来移动第2个盘子，第2个移动完成后，在移动第3个...最终完成第n个的移动。

写了这么多，不知道有没有解析清楚，完成这样一篇文章就是为了和大家分享学习中的心得。同时，朋友们看了之后，有什么地方我思考错了，帮助我指正一下。非常感谢！

独乐乐，不如众乐乐！

写这个文章参考的资料：

http://wenku.baidu.com/link?url=Z94e8n0Lb4m-GcX-8enhs5OWsB0csNh-IOHxLDAtw-3qYDGnkssRyj19OItI0Y9MVAa0zr7PE7bZye56rx6TLcmXu1FnMSsjTAHs16xi5hy

http://blog.csdn.net/qq_21413417/article/details/50531771

感谢以上文章的发表者！