本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-10(57)

2020-11(18)

20190710-汉诺塔算法

发布于2019-08-07 11:25     阅读(192)     评论(0)     点赞(4)     收藏(2)



汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界
的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着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.pythonheidong.com/blog/article/10322/a12777804464847ddf7b/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

4 0
收藏该文
已收藏

评论内容:(最多支持255个字符)