漢諾塔算法

漢諾塔

要想利用遞歸函數(shù)解決問題，一定要完成兩個(gè)基本的要素：遞歸的終止條件，遞推公式。為了分析得到遞歸函數(shù)，下面分三步來考慮這個(gè)問題：

• 說明：A.B.C分別表示三根柱子；1，2，3分別表示三個(gè)圓盤，并且數(shù)字越大表示圓盤越大。
  現(xiàn)在我們需要將A上的全部圓盤移動(dòng)到C上

• ① 只有一個(gè)圓盤：1
  <b>A -> C</b>

• ② 有兩個(gè)圓盤：1、2
  A -> B
  <b>A -> C</b>
  B -> C

• ③ 有三個(gè)圓盤：1、2、3
  A -> C
  A -> B
  C -> B
  <b>A -> C</b>
  B -> A
  B -> C
  A -> C

• 觀察上面的結(jié)果發(fā)現(xiàn)：
  1. 每次最重要的一步，就是將A中最大的圓盤移動(dòng)到C上。
     ①將1：A->C
     ②將2：A->C
     ③將3：A->C
  2. 觀察③：加粗A->C以上部分和以下的部分，我們可以發(fā)現(xiàn)其實(shí)過程和②完全相似。對(duì)于上面的部分：是將1.2兩個(gè)圓盤從起點(diǎn)A移動(dòng)到終點(diǎn)B；對(duì)于下面的部分：是將1.2兩個(gè)圓盤從起點(diǎn)B移動(dòng)到終點(diǎn)C（對(duì)于②：是將1.2兩個(gè)圓盤從A移動(dòng)到C）。
     因此③中的過程，完全可以重復(fù)②的過程實(shí)現(xiàn)。這也就是遞歸的一個(gè)思想。
     這里我們?nèi)绻x一個(gè)函數(shù)，可以這樣表示這個(gè)過程：

#上面部分：n-1個(gè)圓盤從A->B
mov (n-1,A,C,B)
#中間部分
？
#下面部分：n-1個(gè)圓盤從B->C
mov (n-1,B,A,C)

這里就是一個(gè)遞推公式的表現(xiàn)。

3. 最后，遞歸的終止條件：肯定就是回到①中，將每次的最后一個(gè)圓盤從A->C。也就是上述代碼中的中間部分

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

算法實(shí)現(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("請(qǐng)輸入要移動(dòng)的圓盤個(gè)數(shù)：")
mov(int(num),'A','B','C')

程序截圖

參考資料

漢諾塔遞歸算法與解析