- 1、本文档共13页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
递归算法之汉诺塔问题算法分析与设计
一个经典的游戏——汉诺塔问题导入
汉诺塔问题(梵塔问题,TowerofHanoi)汉诺塔来源于一个印度的传说故事:上帝在创造世界时做了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着64片黄金圆盘上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上规定:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘有预言说,这件事完成时地球会在一瞬间毁灭,也有人相信婆罗门至今仍在一刻不停地搬动着圆盘如果移动一个圆盘需要一秒钟,请大家预测一下地球多久之后将毁灭?问题导入
汉诺塔游戏A,B,C3根柱子,n个圆盘,自下而上,由大到小将这n个圆盘从A柱移动到C柱,并且在C柱也需要按照从下往上由大到小的顺序叠放在移动圆盘时应遵守以下移动规则:规则1:每次只能移动1个圆盘规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上规则3:在满足移动规则1和2的前提下,可将圆盘移至A,B,C中任一根柱子上问题导入
汉诺塔游戏1个盘子:直接移动,A?C,1步完成2个盘子:小圆盘,A?B;大圆盘,A?C;小圆盘,B?C,3步完成问题导入原始柱辅助柱目标柱
汉诺塔游戏3个盘子:(1)将两个圆盘由A柱移到B柱(3步完成),(2)将最下面的圆盘由A柱移到C柱(1步完成),(3)将两个圆盘由B柱移到C柱(1步完成),共7步完成问题导入
算法设计设计思路将n个圆盘从A?C,可以分解为3个步骤:(1)将n-1个圆盘从A?B(2)将1个圆盘从A?C(3)将n-1个圆盘从B?CABC
算法设计伪代码Hanoi(n,A,B,C)inputnbeginifn>0Hanoi(n-1,A,C,B)Move(A,C)Hanoi(n-1,B,A,C)end
算法分析时间复杂度分析T(1)=O(1)T(n)=2T(n-1)+O(1)T(n)=(2n–1)×O(1)=O(2n)T(n)=2×2(T(n-2)+O(1))+O(1)=2×2×2T(n-3)+2×2O(1)+2O(1)+O(1)T(n)=2(2n-1–1)+1=2n-1
算法分析时间复杂度分析T(64)=264-1=18446744073709551615,假如每秒钟一次,移动64个圆盘需要多少时间呢?一年,移完这些黄金圆盘需要5800多亿年,比地球寿命还要长
算法实现C/C++语言实现代码#include<stdio.h>intstep;voidmove(intn,chara,charb){ printf("%d:move%dfrom%cto%c.\n",++step,n,a,b);}voidhanoi(intn,chara,charb,charc){if(n>0){hanoi(n-1,a,c,b);move(n,a,c);hanoi(n-1,b,a,c);}}main(){ intn; scanf("%d",&n); hanoi(n,'A','B','C');}1:move1fromAtoC.2:move2fromAtoB.3:move1fromCtoB.4:move3fromAtoC.5:move1fromBtoA.6:move2fromBtoC.7:move1fromAtoC.
课后思考思考题如果有A、B、C、D四根柱子,将n个圆盘从第一根柱子(A柱)全部移动到最后一根柱子(D柱)上,最少需要多少步?
THANKS
您可能关注的文档
- (4.20.1)--4.3.15屋面及防水工程美化.pdf
- (4.15.1)--4.3.10混凝土梁7砌筑工程.pdf
- (4.16.1)--4.3.11混凝土板7砌筑工程.pdf
- (4.11.1)--4.3.6砌筑工程(上)7砌筑工程.pdf
- (4.10.1)--4.3.5桩基工程7砌筑工程.pdf
- (4.21.1)--4.4.1(美化)楼地面1-整体面层及找平层清单工程量计算.pdf
- (4.22.1)--4.4.2(美化)楼地面2-块料、橡塑、其他面层、踢脚线、楼梯、.pdf
- (4.23.1)--4.4.3(美化)墙柱面1-墙面抹灰、柱梁面抹灰、零星抹灰清单工.pdf
- (4.24.1)--4.4.4(美化)墙柱面2-墙面块料、柱梁面块料、零星块料、墙饰.pdf
- (4.25.1)--4.4.5(美化)天棚1-天棚抹灰、吊顶、采光天棚、天棚其他装饰.pdf
- 15+一分钟(名师课件)(七彩课堂)2022至2023学年一年级语文下册同步教学(部编版).pdf
- 14蜗牛(配套课件)2022至2023学年一年级上册语文(小学学霸作业本)部编版.pdf
- 14、蜗牛(课件)可编辑.pdf
- 14.(小蜗牛)(课件)可编辑.pdf
- 14+小蜗牛+共2课时(课件).pdf
- 10绿色的金鱼课件-语文S版-一年级语文上册.pdf
- 1+秋天(配套课件)2022至2023学年一年级上册语文(小学学霸作业本)部编版.pdf
- 1+秋天(课件)可编辑.pdf
- 1+ɑi+ei+ui(配套课件)2022至2023学年一年级上册语文(小学学霸作业本)部编版.pdf
- 1(秋天)(课件)可编辑.pdf
文档评论(0)