鱼C论坛

 找回密码
 立即注册
查看: 1643|回复: 8

[已解决]第24讲:关于汉诺塔的问题

[复制链接]
发表于 2017-3-27 09:54:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. def hanoi(n,x,y,z):
  2.     if n==1:
  3.         print(x,'-->',z)
  4.     else:
  5.         hanoi(n-1,x,z,y)#将前n-1个盘子移动到y上
  6.         print(x,'-->',z)#将最后的移动到z上
  7.         hanoi(n-1,y,x,z)#将y上的n-1个盘子移动到z上
复制代码


这几段代码完全不明白啊
不知道为什么会这么写:
我打个比方
例如我输入
hanoi(3,'a','b','c')
出现以下的形式:
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
谁能解释一下函数是怎么运行的吗?
例如:
hanoi(3,'a','b','c')。
因为n<>1
所以执行
hanoi(2,'a','c','b')
因为你n<>1
所以执行
hanoi(1,'a','b','c')
n=1
所以输出a->c
后面就搞不懂了?
这个问题想了好几天了都弄不懂,谁能帮帮我啊
最佳答案
2017-3-27 11:25:12
我想先说一句话,递归的好处就是能让你忽略处理问题的细节,仔细纠结它是如何处理问题的我认为没必要,只要你有解决方案,在利用递归把问题解决了就好了,以下是你想知道的代码运行过程:
hanoi(3,a,b,c)先执行hanoi(2,a,c,b),后执行print(a-->c),再执行hanoi(2,c,a,b),为了简单表示,我把它简化成:
(3,a,b,c)>(2,a,c,b)>print(a-->c)>(2,c,a,b);
其中(2,a,c,b)>(1,a,b,c)>print(a-->b)>(1,c,a,b)
其中(1,a,b,c)>print(a-->c);(1,c,a,b)>print(c-->b)
我这里就写到hanoi(2,a,c,b)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-3-27 09:55:26 | 显示全部楼层
在线等待,快疯掉了!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 11:25:12 | 显示全部楼层    本楼为最佳答案   
我想先说一句话,递归的好处就是能让你忽略处理问题的细节,仔细纠结它是如何处理问题的我认为没必要,只要你有解决方案,在利用递归把问题解决了就好了,以下是你想知道的代码运行过程:
hanoi(3,a,b,c)先执行hanoi(2,a,c,b),后执行print(a-->c),再执行hanoi(2,c,a,b),为了简单表示,我把它简化成:
(3,a,b,c)>(2,a,c,b)>print(a-->c)>(2,c,a,b);
其中(2,a,c,b)>(1,a,b,c)>print(a-->b)>(1,c,a,b)
其中(1,a,b,c)>print(a-->c);(1,c,a,b)>print(c-->b)
我这里就写到hanoi(2,a,c,b)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 11:59:01 | 显示全部楼层
本帖最后由 隨鈊乄鎍慾 于 2017-3-27 12:02 编辑
赛大爷 发表于 2017-3-27 09:55
在线等待,快疯掉了!


别着急!汉诺塔问题的确没明白想几天也很正常。我当初也想了几天。后来才想明白。用语言讲不太清楚,我尽量说吧怎么说呢?首先你要理解鱼哥的解题思路,其次你把把汉诺塔这个游戏玩得很666;最后跟着鱼哥的思路(就第一步和第三步很重要;第二步较简单)对应到游戏当中去,你就会慢慢的理解了。最后我提醒一下ABC三根柱子之间是在不停的转换角色如:A在第一层是起始位置但在后面的几层里面A会变成目标柱和中转柱;虽然它的名称还是没变还是A,但它的角色变了。汉诺塔的确很绕,但慢慢的你一定也能理解的。
最后总结一下:其实它们(ABC)就是在哪里实现交叉赋值而已!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 12:27:17 | 显示全部楼层
我个人理解递归其实就是数学归纳法。
那需要做的就是两件事:
第一,证明n0的成立,对于汉诺塔而言就是当只有1个盘子而言的时候,怎么做。
第二,假设n时候成立,证明n+1的时候也成立。对于你这个程序而言,就是第n个盘子的时候,让n-1个盘子在y上面,把n从x移到z。就成立了。
中间的具体过程不需要考虑,因为也没必要想。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-27 14:47:03 | 显示全部楼层
18813034116 发表于 2017-3-27 11:25
我想先说一句话,递归的好处就是能让你忽略处理问题的细节,仔细纠结它是如何处理问题的我认为没必要,只要 ...

谢谢你啊,我明白了是怎么运行的了,我这个人就是爱纠结,其实知道没这个必要。谢谢了,以后有问题希望能够再求助你。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-27 14:50:41 | 显示全部楼层
隨鈊乄鎍慾 发表于 2017-3-27 11:59
别着急!汉诺塔问题的确没明白想几天也很正常。我当初也想了几天。后来才想明白。用语言讲不太清楚,我 ...

谢谢你,明白思路了,其实就是三个参数,第一个是 要移动的,第二个是做为辅助的,第三个是目标柱子,完了给它赋值之后他就会他们就会互换角色,当递归到1的时候就全部解出来了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-27 14:52:14 | 显示全部楼层
ooxx7788 发表于 2017-3-27 12:27
我个人理解递归其实就是数学归纳法。
那需要做的就是两件事:
第一,证明n0的成立,对于汉诺塔而言就是当 ...

你这个角度有道理诶,但我有点没转过来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-27 15:05:56 | 显示全部楼层
赛大爷 发表于 2017-3-27 14:50
谢谢你,明白思路了,其实就是三个参数,第一个是 要移动的,第二个是做为辅助的,第三个是目标柱子,完 ...

正解....................
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 17:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表