漢諾塔算法
漢諾塔
要想利用遞歸函數(shù)解決問題瘦癌，一定要完成兩個基本的要素：遞歸的終止條件吼肥，遞推公式。為了分析得到遞歸函數(shù)叠聋，下面分三步來考慮這個問題：
說明：A.B.C分別表示三根柱子撕阎；1，2碌补，3分別表示三個圓盤虏束，并且數(shù)字越大表示圓盤越大。
現(xiàn)在我們需要將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
- 觀察上面的結(jié)果發(fā)現(xiàn)：
- 每次最重要的一步袜啃，就是將A中最大的圓盤移動到C上汗侵。
①將1：A->C
②將2：A->C
③將3：A->C - 觀察③：加粗A->C以上部分和以下的部分，我們可以發(fā)現(xiàn)其實過程和②完全相似。對于上面的部分：是將1.2兩個圓盤從起點A移動到終點B晃择；對于下面的部分：是將1.2兩個圓盤從起點B移動到終點C（對于②：是將1.2兩個圓盤從A移動到C）冀值。
因此③中的過程，完全可以重復②的過程實現(xiàn)宫屠。這也就是遞歸的一個思想列疗。
這里我們?nèi)绻x一個函數(shù)，可以這樣表示這個過程：
- 每次最重要的一步袜啃，就是將A中最大的圓盤移動到C上汗侵。
#上面部分：n-1個圓盤從A->B
mov (n-1,A,C,B)
#中間部分
浪蹂？
#下面部分：n-1個圓盤從B->C
mov (n-1,B,A,C)
這里就是一個遞推公式的表現(xiàn)抵栈。
- 最后，遞歸的終止條件：肯定就是回到①中坤次，將每次的最后一個圓盤從A->C古劲。也就是上述代碼中的中間部分
#中間部分
mov (1,A,B,C)
算法實現(xiàn)
#-*- 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("請輸入要移動的圓盤個數(shù)：")
mov(int(num),'A','B','C')
程序截圖
