首页 > 技术文章 > 经典的 汉诺塔 递归问题

Xlni 2017-01-21 21:38 原文

请编写move(n, a, b, c)函数,它接收参数n,表示3个柱子A、B、C中第1个柱子A的盘子数量,然后打印出把所有盘子从A借助B移动到C的方法,例如:

def move(n, a, b, c):

pass

期待输出:

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

move(3, 'A', 'B', 'C')

直接贴code

def move(n, a, b, c):
if n != 0:
move(n-1,a,c,b)
print('%s --> %s' % (a, c))
move(n-1,b,a,c)

move(3,'a','b','c')
结果如下

a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
意思呢,就是,当我之上还有别的圆盘,就降一维去先移它到过度点b。等之上的都移动走了,我直接移动到c,这就是输出的那句话。
然后呢,我得把之前移开的上一个想办法一回来啊。所以有了最后一句话,把n-1那一维的再想办法从b点移动到c点。

整体逻辑就是这样,它会自己一层层往上推。

大家可以验证

move(n-1,a,c,b)#要把最大的一个从A移到C,那么就需要把前n-1个移到B
move(1,a,b,c)#前n-1个都到B上去了,那就把最底下的那个从A-->B
move(n-1,b,a,c)#移了最底下的,再把B上的n-1个移到C上面就完成了。
为什么传参的顺序是(a,b,c)或者(a,c,b)或者(b,a,c),是因为第一个相当于当前盘子所在的柱子,中间是辅助的柱子,最后一个是目标柱子。

推荐阅读