中瑞祥解析河内塔背景由来以及算法.docx

上传人:p** 文档编号:727231 上传时间:2024-01-29 格式:DOCX 页数:1 大小:14KB
下载 相关 举报
中瑞祥解析河内塔背景由来以及算法.docx_第1页
第1页 / 共1页
亲,该文档总共1页,全部预览完了,如果喜欢就下载吧!
资源描述

《中瑞祥解析河内塔背景由来以及算法.docx》由会员分享,可在线阅读,更多相关《中瑞祥解析河内塔背景由来以及算法.docx(1页珍藏版)》请在第壹文秘上搜索。

1、中瑞祥解析河内塔背景由来以及算法背景由来法国数学家爱德华卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大

2、的顺序。这需要多少次移动呢?这里需要递归的方法假设有n片,移动次数是f(n).显然f(l)=l,f(2)=3,f(3)=7,且f(k+l)=2*f(k)+lo此后不难证明f(n)=2n-l0n=64时,算法介绍其实算法非常简单,当盘子的个数为n时,移动的次数应等于2八n-l(有兴趣的可以自己证明试试看)。后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上,根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放ABC;若n为奇数,按顺时针方向依次摆放ACB。按顺时针方向把圆盘1从现在的柱子

3、移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A0接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘。这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。反复进行(1X2)操作,最后就能按规定完成汉诺塔的移动。所以结果非常简单,就是按照移动规则向一个方向移动金片:如3阶汉诺塔的移动:AC,AB,CB,AC1BA,BC,AC汉诺塔问题也是程序设计中的经典递归问题,下面我们将给出递归和非递归的不同实现源代码。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 高等教育 > 专业基础教材

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!