当然、这是一个经典的递归问题~    　想必来看这篇博文的同学对汉诺塔应该不会陌生了吧， 　　写这篇博还是有初衷的： 　　之前学数据结构的时候自己看书、也上网上查了很多资料，资料都比较散、而且描述的不是很清楚，对于当时刚刚 接触算法的我，要完全理解还是有一定难度。今天刚好有时间就整理了下思路、重写分析了一下之前的疑惑的地方、 没有透彻的地方便都豁然开朗了。所以迫不及待把我的想法记录下来，和大家分享。 　　如果你也是和之前的我一样对hanoi tower没能完全消化，或者刚刚接触汉诺塔，那希望我的这种理解方式能给你些 许帮助，如果你觉得已经完全掌握的比较牢靠了，那也可以看看，有好的idea可以一起分享；毕竟交流讨论也是一种很好的 学习方式。 　　好了，废话不多说，切入正题。 关于汉诺塔起源啊、传说啊神马的就不啰嗦了，我们直接切入正题： 问题描述： 　　有一个梵塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上（如图）。 把这些个盘子从A座移到C座，中间可以借用B座但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘 子始终保持大盘在下，小盘在上。 描述简化：把A柱上的n个盘子移动到C柱，其中可以借用B柱。  　　我们直接假设有n个盘子： 　　先把盘子从小到大标记为1、2、3......n 　　先看原问题三个柱子的状态： 状态0　　A：按顺序堆放的n个盘子。B:空的。C：空的。 　　目标是要把A上的n个盘子移动到C。因为必须大的在下小的在上，所以最终结果C盘上最下面的应该是标号为n的盘子，试想： 要取得A上的第n个盘子，就要把它上面的n-1个盘子拿开吧？拿开放在哪里呢？共有三个柱子：A显然不是、如果放在C上 了，那么最大的盘子就没地方放，问题还是没得到解决。所以选择B柱。当然，B上面也是按照大在下小在上的原则堆放的 **（记住：先不要管具体如何移动，可以看成用一个函数完成移动，现在不用去考虑函数如何实现。这点很重要）。** 　　很明显：上一步完成后三个塔的状态： 状态1： 　　A：只有最大的一个盘子。B：有按规则堆放的n-1个盘子。C空的。 　　上面的很好理解吧，好，其实到这里就已经完成一半了。（如果前面的没懂，请重看一遍。point：不要管如何移动！） 我们继续： 　　这时候，可以直接把A上的最大盘移动到C盘，移动后的状态： 中间状态：　　A：空的。B：n-1个盘子。C：有一个最大盘（第n个盘子） 　　要注意的一点是：这时候的C柱其实可以看做是空的。因为剩下的所有盘子都比它小，它们中的任何一个都可以放在上面，也就是　　　　　　    　　　　　　　　  C柱上。 　　所以现在三个柱子的状态： 中间状态：　　A：空的。B：n-1个盘子。C：空的 　　想一想，现在的问题和原问题有些相似之处了吧？。。如何更相似呢？。显然，只要吧B上的n-1个盘子移动到A，待解决的问题和原问题就相比就只是规模变小了 　　现在考虑如何把B上的n-1个盘子移动到A上，其实移动方法和上文中的把n-1个盘从A移动到B是一样的，只是柱子的名称换了下而已。。（如果写成函数，只是参数调用顺序改变而已）。　 　　假设你已经完成上一步了（同样的，不要考虑如何去移动，只要想着用一个函数实现就好），请看现在的状态： 状态2：　A：有按顺序堆放的n-1个盘子。B：空的。C：按顺序堆放的第n盘子(可看为空柱) 就在刚才，我们完美的完成了一次递归。如果没看懂请从新看一遍，可以用笔画出三个状态、静下心来慢慢推理。 *我一再强调的：当要把最大盘子上面的所有盘子移动到另一个空柱上时，不要关心具体如何移动，只用把它看做一个函数可以完成即可，不用关心函数的具体实现。如果你的思路纠结在这里，就很难继续深入了。* 到这里，其实 基本思路已经理清了。状态2和状态0，除了规模变小 ，其它方面没有任何区别了。然后只要用相同的思维方式，就能往下深入。。。 好了，看看如何用算法实现吧： 定义函数Hanoi（a,b,c,n）表示把a上的n个盘子移动到c上，其中可以用到b。 定义函数move(m,n)表示把m上的盘子移动到n上 我们需要解决的问题正是　　Hanoi (a,b,c,n)   　　//上文中的状态0 1、把A上的n-1个移动到B：  　　Hanoi (a,c,b,n-1);       // 操作结束为状态1 2、把A上的大盘子移动到C         move(a,c)　　　　 3、把B上的n-1移动到A　　　　　Hanoi (b,c,a,n-1);　　//操作结束位状态2(和状态1相比只是规模变小) 如果现在还不能理解、请回过头再看一遍、毕竟如果是初学者不是很容易就能理解的。可以用笔记下几个关键的状态，并且看看你有没有真正的投入去看，独立去思考了。 给出算法C代码：  main() { int n; printf("请输入数字n以解决n阶汉诺塔问题：\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(char A,char B,char C,int n) { if(n==1) { printf("Move disk %d from %c to %c\n",A,C,n); } else { hanoi(A,C,B, n-1); printf("Move disk %d from %c to %c\n",n,A,C); hanoi(B,A,C,n-1,); } } //以上代码c-free5编译通过。 //代码出处：[http://www.cnblogs.com/yanlingyin/](http://www.cnblogs.com/yanlingyin/) 一条鱼~  以上、如果有不对的地方、还希望您能指出。 我对递归的一点理解： 解决实际问题时、不能太去关心实现的细节（因为递归的过程恰恰是我们实现的方法）就像这个问题，如在第一步就过多的纠结于如何把n-1个盘子移动到B上、那么你的思路就很难继续深入。只要看做是用函数实现就好，如果你能看出不管怎么移动，其实本质都一样的时候，那么就能较快的得到结果了。就像这个案例，要注意到我们做的关键几步都只是移动的顺序有改变，其中的规则没有改变，如 如果用函数表示的话，就只是参数调用的顺序有所不同了。在递归的运用中、不用关心每一步的具体实现 ，只要看做用一个函数表示就好。分析问题的时候，最好画出自己的推理过程，得到有效的状态图。 思考问题讲求思路的连贯性、力求尽快进入状态，享受完全投入到一件事中的美妙感觉。 转载请注明出处[http://www.cnblogs.com/yanlingyin/](http://www.cnblogs.com/yanlingyin/)