Python|如何用递归解决汉诺塔问题?

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

n个大小不同的圆盘按照从小到大的顺序放在A柱子上，要求每次搬动1个圆盘，且在搬动过程中，大圆盘在下，小圆盘在上，将所有圆盘从A柱子移动到C柱子，中间可以借助B柱子，请实现搬动过程。

解决方案

1 如果只有一个圆盘

直接从A柱子搬动到C柱子：A->C。

2 如果有2个圆盘

上面小圆盘直接从A搬动到B柱子暂放：A->B；下面大圆盘直接从A搬到C柱子：A->C；B暂放的小圆盘直接搬到C柱子：B->C。

3 如果有3个圆盘

上面2个小圆盘从A搬动到B柱子暂放：H(2,A)->B(A->C;A->B;C->B)；

下面大圆盘直接从A搬到C柱子：A->C；

B暂放的2个小圆盘搬动到C柱子：H(2,B)->C（B->A;B->C;A->C）。

4 规律

1个圆盘直接搬动：原柱子->目的主子；多个圆盘采用汉诺塔搬动方法：圆盘数量，原柱子，目的柱子。

代码示例：

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

#用汉诺塔方法将n个圆盘从a柱子移动到c柱子

if(n<1):

print('圆盘数量错误')

return

if(n==1):

print('{}:{}->{}'.format(n,a,c))

return

hano(n-1,a,c,b)#n-1个圆盘先移动到b柱子

print('{}:{}->{}'.format(n,a,c))#移动最大的那个圆盘

hano(n-1,b,a,c)#n-1个b柱子的圆盘移动到c柱子

hano(4,'a','b','c')

结语

所以得出n个圆盘要搬动2的n次方-1次。其实递归就是直接或间接的调用函数本身，递归主要应用于具有递归关系的问题或者原始问题较复杂，很难求解，但数据量很小容易求解，且大问题和小问题具有相似性。递归可以解决阶乘、汉诺塔等简单问题，也可以用来解决绘制英式标尺等较复杂的问题。

END