Python实现汉诺塔递归算法

汉诺塔算法

要想利用递归函数解决问题，一定要完成两个基本的要素：递归的终止条件，递推公式。为了分析得到递归函数，下面分三步来考虑这个问题：

• 说明：A.B.C分别表示三根柱子；1，2，3分别表示三个圆盘，并且数字越大表示圆盘越大。
  现在我们需要将A上的全部圆盘移动到C上

• ① 只有一个圆盘：1
  <b>A -> C</b>

• ② 有两个圆盘：1、2
  A -> B
  <b>A -> C</b>
  B -> C

• ③ 有三个圆盘：1、2、3
  A -> C
  A -> B
  C -> B
  <b>A -> C</b>
  B -> A
  B -> C
  A -> C

• 观察上面的结果发现：
  1. 每次最重要的一步，就是将A中最大的圆盘移动到C上。
     ①将1：A->C
     ②将2：A->C
     ③将3：A->C
  2. 观察③：加粗A->C以上部分和以下的部分，我们可以发现其实过程和②完全相似。对于上面的部分：是将1.2两个圆盘从起点A移动到终点B；对于下面的部分：是将1.2两个圆盘从起点B移动到终点C（对于②：是将1.2两个圆盘从A移动到C）。
     因此③中的过程，完全可以重复②的过程实现。这也就是递归的一个思想。
     这里我们如果定义一个函数，可以这样表示这个过程：

#上面部分：n-1个圆盘从A->B
mov (n-1,A,C,B)
#中间部分
？
#下面部分：n-1个圆盘从B->C
mov (n-1,B,A,C)

这里就是一个递推公式的表现。

3. 最后，递归的终止条件：肯定就是回到①中，将每次的最后一个圆盘从A->C。也就是上述代码中的中间部分

#中间部分
mov (1,A,B,C)

算法实现

#-*- coding:utf-8 -*-
def mov(n,a,b,c):
    if n== 1:
        print(a,'->',c)
    else:
        mov(n-1,a,c,b)
        mov(1,a,b,c)
        mov(n-1,b,a,c)

num = input("请输入要移动的圆盘个数：")
mov(int(num),'A','B','C')

参考资料

汉诺塔递归算法与解析