请选择 进入手机版 | 继续访问电脑版
爱气象,爱气象家园! 

气象家园

 找回密码
 立即注册

QQ登录

只需一步,快速开始

新浪微博登陆

只需一步, 快速开始

搜索
查看: 2743|回复: 3

汉诺塔问题的简易理解

[复制链接]

新浪微博达人勋

发表于 2018-5-8 10:09:13 | 显示全部楼层 |阅读模式

登录后查看更多精彩内容~

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

x
QQ截图20180508095659.jpg
如果汉诺塔只有3层,显然容易移动
现在图中有8层,将4-8层视为底座的一部分,即不动的,1-3层则可以移动到中间,这时4可以移动到右边,这时,左边的5-8和右边的4都视为固定的,则中间的1-3可以移动到右边,这时我们发现,已经顺利地把1-4移到右边了,而5-8从未动过。
可见,1-4层的塔可以在3个位置自由移动,虽然移动的过程很复杂
这时,我们把1-4塔移动到中间,5盘移到右边,再把1-4塔压在5盘之上,这样就实现了1-5塔的右移。所以,6-7层不动时,1-5塔可以在3个位置随意挪动。
按此规律,可以移动任意层的塔。
密码修改失败请联系微信:mofangbao

新浪微博达人勋

发表于 2018-5-8 10:56:06 | 显示全部楼层
你这是在学python的问题吗
密码修改失败请联系微信:mofangbao

新浪微博达人勋

 楼主| 发表于 2018-5-8 14:11:23 | 显示全部楼层
Eegle 发表于 2018-5-8 10:56
你这是在学python的问题吗

算法是独立于语言的
密码修改失败请联系微信:mofangbao

新浪微博达人勋

 楼主| 发表于 2018-5-9 10:41:26 | 显示全部楼层
汉诺塔移动次数递推公式:
如果左边有n+1个盘子,那么先要将上面n个盘子挪到中间位置,再把底盘放右边,然后把中间的塔压右边,设n个盘子的整体移动需要的移动次数是f(n),那么这次搬动的移动次数,即f(n+1)=2*f(n)+1
这是个求数列通项公式的典型题目:
变形:
f(n+1)+1=2*f(n)+1+1=2*(f(n)+1)
设g(n)=f(n)+1,则g(n+1)=2*g(n),显然g(n)是个公比为2的等比数列,且g(1)=f(1)+1=2
......
结果为f(n)=2^n-1
可见汉诺塔问题跟象棋格子放稻子有一拼,阿三的数学有一套!
密码修改失败请联系微信:mofangbao
您需要登录后才可以回帖 登录 | 立即注册 新浪微博登陆

本版积分规则

Copyright ©2011-2014 bbs.06climate.com All Rights Reserved.  Powered by Discuz! (京ICP-10201084)

本站信息均由会员发表,不代表气象家园立场,禁止在本站发表与国家法律相抵触言论

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