20190710-汉诺塔算法
2019-07-24 09:19:08来源:博客园 阅读 ()
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界
的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵
天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘
上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
关键点:
一次只能移动一个盘子
大盘不能重叠在小盘子上
当n=1的时候
1. 直接将1从X移动到Z
当n=2的时候
1. 将1从X移动到Y轴
2. 将2从X移动到Z轴
3. 将1从Y移动到Z轴
当n=3的时候
1. 将1从X移动到Z
2. 将2从X移动到Y
3. 将1从Z移动到Y
4. 将3从X移动到Z
5. 将1从Y移动到X
6. 将2从Y移动到Z
7. 将1从X移动到Z
当n=4的时候
当前挪动的盘子为1,挪动轨迹为x==>y
当前挪动的盘子为2,挪动轨迹为x==>z
当前挪动的盘子为1,挪动轨迹为y==>z
当前挪动的盘子为3,挪动轨迹为x==>y
当前挪动的盘子为1,挪动轨迹为z==>x
当前挪动的盘子为2,挪动轨迹为z==>y
当前挪动的盘子为1,挪动轨迹为x==>y
当前挪动的盘子为4,挪动轨迹为x==>z
当前挪动的盘子为1,挪动轨迹为y==>z
当前挪动的盘子为2,挪动轨迹为y==>x
当前挪动的盘子为1,挪动轨迹为z==>x
当前挪动的盘子为3,挪动轨迹为y==>z
当前挪动的盘子为1,挪动轨迹为x==>y
当前挪动的盘子为2,挪动轨迹为x==>z
当前挪动的盘子为1,挪动轨迹为y==>z
总结规律为:
要想移动n个盘子从X轴到Z轴需要经过如下三步:
1. 将n-1个盘子从X轴移动到Y轴
2. 将第n个盘子从X轴移动到Z轴
3. 将n-1个盘子从Y轴移动到Z轴
转换为算法
• 递归的结束条件:
• 当n=1的时候,直接将n移动到Z轴
• 递归条件:
1. 将n-1个盘子从X轴移动到Y轴
2. 将第n个盘子从X轴移动到Z轴
3. 将n-1个盘子从Y轴移动到Z轴
代码
def hannota(n,x,y,z): if n ==1: print('%s->%s'%(x,z))#当n=1的时候,直接将n移动到z轴 else: hannota(n-1,x,z,y)#将n-1个盘子从X轴移动到Y轴 print('%s->%s'%(x,z))#将第n个盘子从X轴移动到Z轴 hannota(n-1,y,x,z)#将n-1个盘子从Y轴移动到Z轴 hannota(3,'x','y','z')
原文链接:https://www.cnblogs.com/hyj691001/p/11167032.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:数据表管理admin
下一篇:docker学习记录
- Python用摘要算法生成token及检验token 2019-07-24
- python算法与数据结构-二叉树的代码实现(46) 2019-07-24
- python算法与数据结构-数据结构中常用树的介绍(45) 2019-07-24
- python算法与数据结构-栈(43) 2019-07-24
- python算法与数据结构-队列(44) 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash