鱼C论坛

 找回密码
 立即注册
查看: 1895|回复: 148

[知识点备忘] S1E35:汉诺塔

  [复制链接]
最佳答案
229 
发表于 2016-11-24 04:38:00 | 显示全部楼层 |阅读模式

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

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

x
知识点回顾

原始状态下的汉诺塔如下:

1.png

Step1 X->Z:

2.png

Step2 X->Y:

3.png

Step3 Z->Y:

4.png

Step4 X->Z:

5.png

Step5 Y->X:

6.png

Step6 Y->Z:

7.png

Step7 X->Z:

8.png

对于上述游戏的玩法,可以简单分解为三个步骤:

  • 将前 63 个盘子从 X 移动到 Y上,确保大盘在小盘下。
  • 将最底下的第 64 个盘子从 X 移动到 Z 上。
  • 将 Y 上的 63 个盘子移动到 Z 上。

在游戏中,由于每次只能移动一个圆盘,所以在移动的过程中显然要借助另外一根针才可以实施。也就是说,步骤 1 将 1~63 个盘子移到 Y 上,需要借助 Z;步骤 3 将 Y 针上的 63 个盘子移到 Z 针上,需要借助 X。

所以我们把新的思路聚集为以下两个问题:

  • 问题一:如何将 X 上的 63 个盘子借助 Z 移到 Y 上?
  • 问题二:如何将 Y 上的 63 个盘子借助 X 移到 Z 上?

解决这两个问题的方法跟解决“如何将 X 上的 64 个盘子借助 Y 移动到 Z 上?”这个问题是一样的,都是可以拆解成 1、2、3 三个步骤来实现。

问题一(“如何将 X 上的 63 个盘子借助 Z 移到 Y 上?”)拆解为:

  • 将前 62 个盘子从 X 移动到Z上,确保大盘在小盘下。
  • 将最底下的第 63 个盘子移动到 Y 上。
  • 将 Z 上的 62 个盘子移动到 Y 上。

问题二(“如何将 Y 上的 63 个盘子借助 X 移到 Z 上?”)拆解为:
  • 将前 62 个盘子从 Y 移动到 X 上,确保大盘在小盘下。
  • 将最底下的第 63 个盘子移动到 Z 上。
  • 将 X 上的 62 个盘子移动到 Y 上。

没错,汉诺塔的拆解过程刚好满足递归算法的定义,因此,对于如此难题,使用递归来解决,问题就变得相当简单了!

回复“朕想知道”给你看源代码!

游客,如果您要查看本帖隐藏内容请回复


本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2016-12-13 21:14:05 | 显示全部楼层
沙发
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-9-22 23:16:21 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2017-10-1 14:29:10 | 显示全部楼层

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-3 12:53:01 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-6 23:21:19 | 显示全部楼层
666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1287 
发表于 2017-10-18 10:42:22 | 显示全部楼层
好好学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-18 21:32:58 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-19 23:23:48 | 显示全部楼层
真想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-22 15:48:11 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-10-23 22:05:27 | 显示全部楼层
想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1 
发表于 2017-10-30 16:57:46 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-1 10:06:11 | 显示全部楼层
haha
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-3 22:04:13 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-8 16:25:48 | 显示全部楼层
谢谢~~~~~~~~~~~~~~~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-12 10:41:08 From FishC Mobile | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
3 
发表于 2017-11-13 16:00:08 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-14 18:03:12 | 显示全部楼层
朕想知道!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-14 18:11:03 | 显示全部楼层
朕想知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
发表于 2017-11-15 10:52:29 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-9-25 16:10

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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