QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

管理员

Rank: 40Rank: 40Rank: 40Rank: 40Rank: 40Rank: 40

技术值
查看: 774|回复: 46

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

[复制链接]
最佳答案
191 
累计签到:2285 天
连续签到:16 天
小甲鱼 发表于 2016-11-24 04:38:00 77446 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

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

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 上。

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

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

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


本帖被以下淘专辑推荐:

楼层
跳转到指定楼层
最佳答案
0 
累计签到:61 天
连续签到:2 天
jamespp 发表于 2016-12-13 21:14:05 | 显示全部楼层
沙发
最佳答案
0 

尚未签到

lansong747q 发表于 2017-9-22 23:16:21 | 显示全部楼层
最佳答案
1 
累计签到:51 天
连续签到:1 天
还差几 发表于 2017-10-1 14:29:10 | 显示全部楼层

最佳答案
0 
累计签到:74 天
连续签到:1 天
■愛祢ゝ①丗 发表于 2017-10-3 12:53:01 | 显示全部楼层
朕想知道
最佳答案
0 
累计签到:164 天
连续签到:1 天
清水2918 发表于 2017-10-6 23:21:19 | 显示全部楼层
666
最佳答案
537 
累计签到:212 天
连续签到:61 天
BngThea 发表于 2017-10-18 10:42:22 | 显示全部楼层
好好学习一下
最佳答案
0 
累计签到:32 天
连续签到:1 天
Z同学 发表于 2017-10-18 21:32:58 | 显示全部楼层
朕想知道
最佳答案
0 
累计签到:32 天
连续签到:2 天
家丁 发表于 2017-10-19 23:23:48 | 显示全部楼层
真想知道
最佳答案
0 
累计签到:4 天
连续签到:1 天
q592697384 发表于 2017-10-22 15:48:11 | 显示全部楼层
朕想知道
最佳答案
0 

尚未签到

BT鸡翅 发表于 2017-10-23 22:05:27 | 显示全部楼层
想知道
最佳答案
1 
累计签到:80 天
连续签到:2 天
fwinmachao 发表于 2017-10-30 16:57:46 | 显示全部楼层
朕想知道
最佳答案
0 
累计签到:21 天
连续签到:1 天
lssfishc 发表于 2017-11-1 10:06:11 | 显示全部楼层
haha
最佳答案
0 
累计签到:20 天
连续签到:2 天
MaxChan 发表于 2017-11-3 22:04:13 | 显示全部楼层
朕想知道
最佳答案
0 
累计签到:9 天
连续签到:1 天
yc5780 发表于 2017-11-8 16:25:48 | 显示全部楼层
谢谢~~~~~~~~~~~~~~~~
最佳答案
0 

尚未签到

srwh2000 发表于 2017-11-12 10:41:08 From FishC Mobile | 显示全部楼层
朕想知道
最佳答案
2 
累计签到:39 天
连续签到:1 天
payton24 发表于 2017-11-13 16:00:08 | 显示全部楼层
朕想知道
最佳答案
0 
累计签到:16 天
连续签到:1 天
yzx3824 发表于 2017-11-14 18:03:12 | 显示全部楼层
朕想知道!
最佳答案
0 
累计签到:82 天
连续签到:2 天
TZD777 发表于 2017-11-14 18:11:03 | 显示全部楼层
朕想知道
最佳答案
1 
累计签到:48 天
连续签到:5 天
高价回收穷鬼盾 发表于 2017-11-15 10:52:29 | 显示全部楼层

发表回复

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

本版积分规则

关闭

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

    移动客户端下载(未启用)
    微信公众号

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

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2018-1-16 23:31

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