20190710-汉诺塔算法
发布于2019-08-07 11:25 阅读(690) 评论(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黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力