汉诺塔的思考及解答

其实在汉诺塔问题之前，斐波那契数列的问题是个比较好解决的问题。

但是汉诺塔问题令我思考了一段时间。最后不断探索，有了一些思考。

沉下心，我们需要有一个大的格局。不断分解为小的问题。

递归问题么，不就是找到规律与出口么。

汉诺塔（又称河内塔）问题：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

我们不妨自己先试一试，如何将一个或三个盘子从a移动到c。

好的，那么总结一下规律，假设有n个盘子，我们就是借助一个柱子c，把a上的n-1个盘子放到b上，再把b上的n-1个盘子通过a移动到c上即可。（下图较复杂，简单看看就好）

好的，那么这一步的代码该怎么写呢？？？

hanoi(n-1,a,c,b);//我们就是借助一个柱子c，把a上的n-1个盘子放到b上，
printf("将%c移动到%c\\n",a,b);
hanoi(n-1,b,a,c);//再把b上的n-1个盘子通过a移动到c上即可。

这样是不是就可以理解了。

好的，但是我们要给这个函数一个出口不然，他就会一直跑下去。。。（并且问我怎么知道的）

if(n==1){//终止条件。
printf("将%c移动到%c\\n",a,c);//最后不就是把a上的最后一个放到c上，就可以了吧。
//我们不考虑别的。嘿嘿
}

那么综合起来就是：

#include<stdio.h>
int cnt;
int hanoi(int n,char a,char b,char c){
cnt++;
if(n==1){
printf("将%c移动到%c\\n",a,c);
}
else {
hanoi(n-1,a,c,b);
printf("将%c移动到%c\\n",a,b);
hanoi(n-1,b,a,c);
}
}
int main(){
int n;
char a='a',b='b',c='c';
scanf("%d",&n);
hanoi(n,a,b,c);
printf("%d",cnt);
}

注释可以参考上面的哦。

链接：知乎上有一个有意思的答案，不妨一看：

https://www.zhihu.com/question/24385418/answer/257751077

bilibili也有一个不错的视频讲解：

https://www.bilibili.com/video/av9830115?from=search&seid=9898738544530212324