- 前言
- 一、解决思路是什么
- 二、C语言实现汉诺塔问题
- 1.代码示例
- 2.代码运行结果
- 总结
前言
汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则:
1.每次只能移动柱子最顶端的一个圆盘;
2.每个柱子上,小圆盘永远要位于大圆盘之上;
一、解决思路是什么
目标:将n个盘子从A柱移动到C柱
分析:不管前面的n-1个盘子怎么样移动,我们肯定最先得把最下面的第n个盘子移动到C柱上。
所以步骤如下
第一步:将前n-1个盘子看成一个整体,从A柱(起始柱),经由C柱(工具柱),移动到B柱(目标柱),我们不管n-1个盘子移动的过程是怎么样的
第二步:将第n个盘子从A(起始柱),移动到C(目标柱)
第三步:将n-1个盘子,从B柱(起始柱),经由A柱(工具柱),移动到C柱(目标柱)
有些同学到这就有些不理解了,那第三步的n-1个盘子是怎么移动C柱的呢?
第三步展开
目标:将n-1个盘子从B柱移动到C柱
分析:不管前面的n-2个盘子怎么样移动,我们肯定最先得把最下面的第n-1个盘子移动到C柱上。
所以步骤如下
首先:将前n-2个盘子看成一个整体,从B柱(起始柱),经由C柱(工具柱),移动到A柱(目标柱),我们不管n-1个盘子移动的过程是怎么样的
其次:将第n-1个盘子从B(起始柱),移动到C(目标柱)
最后:将n-2个盘子,从A柱(起始柱),经由B柱(工具柱),移动到C柱(目标柱)
从第三步的单独分析可以看出,其实第三步的整体思路和之前两步一样,只不过起始柱,工具柱和目标柱变了
从这里可以看出我们又回到了最初的问题,只不过盘子由n个变成了n-2个。
接下来的操作便和A柱上n个盘子时候操作一样。如此循环往复便能把盘子全部移到C上。这便涉及到了函数递归的思想
相信大家看到这里也明白了n个盘子的移动过程是怎么样的,那么代码怎么写呢?
#define _CRT_SECURE_NO_WARNINGS 1 #include2.代码运行结果void move(int n, char x, char y, char z) //move(移动个数,起始柱,工具柱,目标柱) { if (n == 1)//当盘子只有一个的时候其实不用 //进行其它操作直接从起始柱移动到目标柱上即可 //这也是函数的递归出口 printf("%d form %c to %cn", n, x, z); else { move(n - 1, x, z, y);//第一步 printf("%d form %c to %cn", n, x, z); //第二步 move(n - 1, y, x, z);//第三步 } } int main() { int n = 0; printf("请输入盘子个数:"); scanf("%d", &n); printf("移动步骤如下:n"); move(n, 'A', 'B', 'C'); return 0; }
当n=1时,代码输出结果:
当n=2时,代码输出结果:
当n=3时,代码输出结果:
代码就展示1-3的盘子个数,想要试验其它的盘子个数大家可以自己去试验。
总结
理解汉诺塔问题的关键,是理解它的移动过程然后把它转化成递归思想,从本质上去理解问题。找到我们必须做的几点如:不管前面的盘子怎么移动,最大的盘子必须从起始柱移动到目标柱。这个是我们理解汉诺塔问题最关键的一步。
如果大家不理解汉诺塔程序是如何运行的话,大家评论留言我可以出一期汉诺塔程序运行的详解,为大家解惑。