鱼C论坛

 找回密码
 立即注册
查看: 3370|回复: 14

[技术交流] (原创首发)递归典型——汉诺塔问题详解

[复制链接]
发表于 2018-6-12 11:03:33 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 BngThea 于 2018-6-14 22:29 编辑

递归问题本身就是容易困扰新手的一个难点,其实很多时候,能不写递归就别写递归
从节能角度来看,效率并不高效,甚至很低
但是以下情况请使用递归:
1 展示才(zhuang)能(bi)
2 其他方法逻辑太过困难,比如汉诺塔问题


汉诺塔问题是初学递归时遇到的较难的问题,详细描述请参考小甲鱼老师的这篇讲解:
http://bbs.fishc.com/thread-79183-1-1.html

本文将重点讲解一个3级的递归实现过程
其实,难就难在理解3级,如果3级理解了,后面的n级只不过是依葫芦画瓢而已

先看代码实现:
  1. def h(n,x,y,z):
  2.     if n == 1:
  3.         print(x,"-->",z)
  4.     else:
  5.         h(n-1,x,z,y)     #将n-1个盘子从x移动到y上
  6.         print(x,"-->",z) #将最底下的最后一个盘子从x移动到z上
  7.         h(n-1,y,x,z)     #将y上的n-1个盘子移动到z上

  8. h(3,'x','y','z')
复制代码

结果:
  1. x --> z
  2. x --> y
  3. z --> y
  4. x --> z
  5. y --> x
  6. y --> z
  7. x --> z
复制代码


递归要点: 递归时,一旦进入递归,后续代码暂时挂起,等回归的时候继续执行
汉诺塔难点: 递归过程中实参的不断变换

以 n==3 作为示例,请特别注意实参的变化(为简单起见,print格式随意了)
1  h(3,x,y,z)开始,判断if,此时n==3 if条件不成立, 进入else

2  执行 h(2,x,z,y) #特别注意:此时形参和实参的对应关系是 x-x,y-z,z-y
        2.1 n==2,进入else,执行h(1,x,y,z) #注意实参的匹配
                print x-->z 然后返回
        2.2 print x-->y
        2.3 执行h(1,z,x,y)#注意实参的匹配
                print z-->y 然后返回
        返回到h(3,x,y,z)

3 print x-->z

4 执行 h(2,y,x,z) #特别注意:此时形参和实参的对应关系是 x-y,y-x,z-z
        4.1 n==2,进入else,执行h(1,y,z,x) #注意实参的匹配
                print y-->x 然后返回
        4.2 print y-->z
        4.3 执行h(1,x,y,z)#注意实参的匹配
                print x-->z 然后返回
        返回到h(3,x,y,z)
程序结束

从上面看来,打印结果就是紫色字体的顺序排列
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-6-14 21:28:39 | 显示全部楼层
请指教下第三步骤是执行哪个代码来的   3 print x-->z,返回到h(3,x,y,z)但是3不等于1啊,这个print x-->z是哪里来的?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-14 21:42:17 | 显示全部楼层
看明白了那段代码分了两段执行的是 print(x,"-->",z) #将最底下的最后一个盘子从x移动到z上这个代码。被绕进去了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-6-14 21:59:15 | 显示全部楼层
chongchuigu 发表于 2018-6-14 21:28
请指教下第三步骤是执行哪个代码来的   3 print x-->z,返回到h(3,x,y,z)但是3不等于1啊,这个print x-->z ...

n==3的时候,第一部分n==2的递归已经完成后的print语句
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-14 22:08:42 | 显示全部楼层
老司机,赞
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-14 22:14:43 | 显示全部楼层
个别地方有笔误,
  1. 1  h(3,x,y,z)开始,判断if n==3不成立, 进入else
复制代码
这里1写成为3了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-6-14 22:24:52 | 显示全部楼层
myckjx 发表于 2018-6-14 22:14
个别地方有笔误,这里1写成为3了

不是笔误,是少了个逗号,意思是判定if
此时n为3,所以不成立
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-14 23:50:39 | 显示全部楼层
还是看不太懂,我自己研究了很久,总结了一些东西不知道对不对,等会发个菜鸟贴子汇报一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-28 16:53:33 | 显示全部楼层
“2  执行 h(2,x,z,y) #特别注意:此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来,但是代码为什么是这样写 看不懂,为什么是h(2,x,z,y) 而不是别的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-6-28 17:01:58 | 显示全部楼层
keweel 发表于 2018-6-28 16:53
“2  执行 h(2,x,z,y) #特别注意:此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来 ...

因为此时要将x上的盘子移动到y上去,通过z
根据之前的分析,也就是 x, z, y
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-18 14:57:13 | 显示全部楼层
为什么"2.1 n==2,进入else,执行h(1,x,y,z) #注意实参的匹配"这里不是执行h(1,x,z,y)呢????
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-4-19 08:36:25 | 显示全部楼层
mhb789456 发表于 2019-4-18 14:57
为什么"2.1 n==2,进入else,执行h(1,x,y,z) #注意实参的匹配"这里不是执行h(1,x,z,y)呢????

是执行h(1,x,z,y),但是形参对应的变量发生了变化,也就是h(1,x=x,z=y,y=z),即h(1,x,y,z)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-22 14:38:54 | 显示全部楼层
BngThea 发表于 2019-4-19 08:36
是执行h(1,x,z,y),但是形参对应的变量发生了变化,也就是h(1,x=x,z=y,y=z),即h(1,x,y,z)

也就是说每次传递参数都是x,y,z吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-22 18:37:00 | 显示全部楼层
666666666666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-28 21:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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