用Python实现汉诺塔游戏的简单步骤
最编程
2024-07-28 08:59:23
...
汉诺塔
有三根柱子A、B、C,柱子A上从下到上从大到小摞着n个圆盘。要求将全部圆盘挪动到另一根柱子C,并且大盘始终不能放在小盘上面,且一次只能移动一个圆盘。
方法:
将ABC摆成品字型。当n为偶数时,顺时针顺序为ABC;当n为奇数时,顺时针顺序为ACB。
step (2i+1): 顺时针移动最小圆盘1
step (2i+2): 将非空柱子上的圆盘移动到空柱子,原则是,移动可移动的最大圆盘,且当C柱子已按顺序摆有圆盘n~(n-x)时,当C为空柱子。
总移动次数为:f(n)=2*f(n-1)+1=2^n-1
递归算法原理:
step 1:将上面的n-1个圆盘从A移到B,借助C move(n-1, a,c,b)
step 2:将最下面的圆盘从A直接移到C print(a, '-->', c)
step 3:将n-1个圆盘从B移到C,借助A move(n-1, b,a,c)
step 4:当只有一个圆盘时,直接从A移到C print(a, '-->', c)
# -*- coding: utf-8 -*-
def move(n, a, b, c):
if(n==1):
print(a, '-->', c) #step 4
else:
move(n-1, a, c, b) #step 1
print(a, '-->', c) #step 2
move(n-1, b, a, c) #step 3
#test
move(3,'A','B','C')
结果:
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
上一篇: Echarts 3D地图下钻
下一篇: 探索者Zimovv的个人博客空间