汉诺塔算法
汉诺塔
要想利用递归函数解决问题，一定要完成两个基本的要素：递归的终止条件，递推公式。为了分析得到递归函数，下面分三步来考虑这个问题：
说明：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
- 观察上面的结果发现：
- 每次最重要的一步，就是将A中最大的圆盘移动到C上。
①将1：A->C
②将2：A->C
③将3：A->C - 观察③：加粗A->C以上部分和以下的部分，我们可以发现其实过程和②完全相似。对于上面的部分：是将1.2两个圆盘从起点A移动到终点B；对于下面的部分：是将1.2两个圆盘从起点B移动到终点C（对于②：是将1.2两个圆盘从A移动到C）。
因此③中的过程，完全可以重复②的过程实现。这也就是递归的一个思想。
这里我们如果定义一个函数，可以这样表示这个过程：
- 每次最重要的一步，就是将A中最大的圆盘移动到C上。
#上面部分：n-1个圆盘从A->B
mov (n-1,A,C,B)
#中间部分
？
#下面部分：n-1个圆盘从B->C
mov (n-1,B,A,C)
这里就是一个递推公式的表现。
- 最后，递归的终止条件：肯定就是回到①中，将每次的最后一个圆盘从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')
程序截图
