递归算法"/>
python递归算法
python递归算法 - 汉诺塔问题
经典汉诺塔问题:
有三根柱子a,b,c,在一根柱子a上,从下往上按照从大到小的顺序摞着64片黄金圆盘。把所有圆盘从下往上按从大到小的顺序重新摆放在另一根柱子c上。并且规定,小圆盘只能放在大圆盘上,在三根柱子之间每次只能移动一个圆盘。
问:
移动完所有圆盘从a到c,需要移动多少次,设计程序记录移动的步骤
图例3.8:以三个圆盘为例,实现递归
算法实现步骤:
(最下面的一个盘子记为N,上面的所有盘子记为N-1,看做一个整体)
N个盘子时
1.把N-1个盘子从A经过C移动到B
hannoi(N-1,A,C,B)
2.把第N个圆盘从A移动到C
print("moving from %s to %s" % (a, c))
3.把N-1个盘子从B经过A移动到C
hannoi(N-1,B,A,C)
完整代码如下:
def hanoi(n, a, b, c):#定义一个汉诺函数,n个盘子,a,b,c三根柱子if n > 1:#圆盘数大于1时hanoi(n - 1, a, c, b)#自调用函数,把N-1个盘子从A经过C移动到Bprint("moving from %s to %s" % (a, c))#把第N个圆盘从A移动到Chanoi(n - 1, b, a, c)#自调用函数,把N-1个盘子从B经过A移动到C
测试:5个盘子
hanoi(5, "a", "b", "c")
输出结果:
更多推荐
python递归算法
发布评论