python中的漢諾塔遞歸演算法的具體運算過程是怎樣的？

01-05

def move(n,a,b,c): if n==1: print(a,"-&>",c) else: move(n-1,a,c,b) move(1,a,b,c) move(n-1,b,a,c) move(3,"A","B","C")
想不通，很煩惱！希望能有人為我解惑。

重點其實是：不要一開始就關心每一步怎麼解決的，你只需要把函數當成一個實現你目的的神器，隨時調用。也就是遞歸。

比如說我們有一個萬能神器move，只需要給它幾個參數，即可自動完成一個功能：把n個盤子利用緩衝區，從起點運送到終點，期間嚴格遵守漢諾塔規則。

這裡你暫時不需要去了解每一個步是如何實現的。

move(N,起點，緩衝區，終點）
N: 盤子的個數。

現在有個n個盤子，a,b,c三個塔。

把n個盤子抽象成兩個盤子，n-1 和底下最大的1

n = (n-1) + 1

這個最簡單的玩法如何實現呢

首先：把n-1 移到緩衝區 -------過程1

然後：把1 移到終點 -------過程2

最後：把緩衝區的n-1 移到終點 -------過程3

過程1 如何實現？

還是召喚神器吧。

move(N,起點，緩衝區，終點）

此時，我們的起點是a,終點是b ,N=n-1,緩衝區只能是c了

move(n-1,a,c,b)

過程2呢？

move(1,a,b,c)

過程3呢？

move(n-1,b,a,c)

哦哦神器的力量太大，止不住咋辦。。

if (N == 1):
a -&> c #此時我已經不需要緩衝區了

剛才似乎開竅了，不知道這樣表達是否正確？

...........................................................................................print

.......................................................↗move(1,"A","B","C")...A--&>C

.......................... move(2,"A","C","B")→move(1,"A","C","B")...A--&>B

.............................↗.......................↘move(1,"C","A","B")...C--&>B

move(3,"A","B","C")→move(1,"A","B","C") .............................A--&>C

.............................↘........................↗move(1,"B","C","A")...B--&>A

............................move(2,"B","A","C")→move(1,"B","A","C")...B--&>C

..........................................................↘move(1,"A","B","C)...A--&>C

謝謝@phil chang 的解答！

這個問題其實設置幾個斷點運行一下就能搞明白。

首先我們要明確一個概念，遞歸函數是從哪個函數開始運行之後就要返回哪個函數。

def move(n,a,b,c): if n==1: print(a,"-&>",c) else: move(n-1,a,c,b) move(1,a,b,c) move(n-1,b,a,c)

我們先以n=2為例：

注意參數的變化。

第一步運行至if語句，判斷n不等於1。

進入else分支，運行move(n-1,a,c,b)函數。

由於move(n-1,a,c,b)函數也是move函數，只是參數發生變化，所以仍需回到move函數的最初運行，注意此時參數已經變成如上的樣子。

再往下繼續運行，運行至if進行判斷。

符合if條件，繼續往下運行，此時列印a-&>c，相當於把A柱最上層的圓盤放到了B柱上。

注意！此時繼續往下運行又回到了else分支中的第一個move函數，參數也變成了開始時候的樣子，這裡就是開始時說的遞歸函數從哪個函數開始運行就返回哪個函數。

繼續運行至下一行。

此時運行move(1,a,b,c)，參數發生變化。

又運行到if，進行判斷。

符合條件，列印a-&>c，相當於把A柱上第二個圓盤放到了C柱上。

列印之後返回move(1,a,b,c)。

向下繼續運行至move(n-1,b,a,c)。

參數再次發生變化。

if語句進行判斷。

符合條件，列印a-&>b，相當於將B上的圓盤（也就是A柱最上面一塊的圓盤）放到了C柱上。

再返回move(n-1,b,a,c)，再向下運行，此時函數運行結束。

直接運行的結果是這樣的：

n=3的時候也是一樣，用斷點自己跑一邊程序再看看差不多就沒問題了，其中最不好理解的可能就是沒有理解遞歸函數的含義，對返回這一點認識不清。

別問我這函數是怎麼寫出來的，我是寫不出來這函數的（捂臉逃）

每一步的遞歸都要從演算法的開頭進行，到出現輸出為止。放到這個演算法中就是每一次move都要從開頭進行計算，到n==1為止。具體運算過程是這樣的:

然後，讓我們來理解代碼。

從第五行開始。第五行表示要把除最大的盤子以外的其它通過過度柱c從起始柱a放到終點柱b。

第六行表示將最大的盤子從起始柱a放到終點柱c。

然後第七行表示把除最大的盤子之外的其他盤子從起點柱b通過過度柱a放到終點柱c。

然後最大的盤子到達最終目標點c之後，要保證最優步驟，就不需要再移動它，忽略不計。單純考慮要達成第五行和第七行目標需要進行的步驟。你會發現這是改變了起始，過度和終點的又一次重複。

# Tower of Hanoi # Three towers A, B, C # All discs start with A # Goal: move all discs to C # Rule: # 1. Can only move one disc at a time # 2. Larger disc can never cover up a small disc


def move(n, fr, sp, to):

    """

    fr: from, tower A

    sp: spare, tower B

    to: to, tower C

    """

    if n == 1:

        # if only one disc in A

        # just move it to C

        print(fr, "-&>", to)

    else:

        # otherwise do recursion

        # move all (n-1) discs except bottom one

        # from A to B

        move(n - 1, fr, to, sp)

        # move the bottom (1) disc

        # from A to C

        move(1, fr, sp, to)

        # move the rest (n-1) discs

        # from B to C

        move(n - 1, sp, fr, to)

move(3, "A", "B", "C")

帶了註解，希望能幫助理解

漢諾塔是將所有盤子（n個）從A柱挪至C柱，大盤必須在小盤下方。

思路為將n-1個盤子（除了最底下一枚）從A移到B（第一步）; 然後將位於A的最後一枚最大盤移至C（第二步）; 再將B柱上所有盤移至C柱（第三步）。

1.def move（n,a,b,c）: #便是設定總路徑為將n個盤從a柱藉由b柱最終移至c。

2. ____if n==1: #n值為1 而非定義n=1

3. ________print(a, "-&>", c) #是在僅為一個盤的情況下從得出a-&>c的結果，在輸入指令 move(3,"A","B","C") 的情況下即是得出結果A-&>C

4. ____else:

5. ________move(n-1,a,c,b) #是指代將n-1個盤從a處經由c移至b（第一步）；

6. ________move(1,a,b,c) #可替換為print(a,"-&>",c)，因為只是將A柱底最大盤移至C柱的過程（第二步）；

7. ________move(n-1,b,a,c) #是指代將位於b處的n-1個盤從b經由a移至c （第三步）

看似簡單但循環下來其實是很有邏輯和條理的。

代碼第5、7行為遞歸函數的體現，在n-1&>1的情況下先運行move(n-1,a,c,b)至n-1==1,得出a -&> c的結果（a -&> c不等於A -&> C）。具體流程拆解@淺淺的回答已經很清楚了。

當第5行遞歸執行完畢後進入第6行打出必然結果A -&> C.

第7行同理。

值得注意的是函數執行的順序和參數的含義。

剛好看到這個遞歸經典問題。

著重說else裡面最不容易理解的三行代碼。

再複雜的漢諾塔，實際上就是兩層(樓上已經回答了)。基座1和上面n-1塊

相信大家困擾的是else內的三行代碼。

step 1:

把上面那部分n-1從a針挪動到b針

你傳進去的參數順序

hanoi(n-1,a,c,b)

遞歸調用原函數 and 把參數傳到下面

hanoi(n-1,a,b,c)

調用方法應該列印 a---&>c

這時候要看好了 b，c參數實際上已經調換位置了

也就是原形參b的位置是實參c了，形參c的位置是b了

這時候調用形參a---c

事實上最後列印出來就是實參的a---&>b

step 2：

print(a，"----&>",c)

把基座從a針挪動到c針

step 3：

把上面那部分n-1從b針挪動到c針

你傳進去的參數順序

hanoi(n-1,b,a,c) 然後遞歸

調用原函數 and 把參數傳到下面

hanoi(n-1,a,b,c)

調用方法應該列印 b---&>c

該問題就是就是比較抽象，需要把傳參搞明白

我這個解釋，可能要比上面回答更容易看懂最難理解的三行代碼。

如果幫助你迅速理解了，那就

用了一個下午最後畫了個圖明白了，這是三個木板的函數循環過程，感覺挺清楚的

恰巧我也在遇到這個問題了, 我的理解是在設置函數參數的時候, 已經默認了很多設置. 這個函數用用漢語來說是move(盤數, 起始位置, 臨時位置, 目標位置).

所以第五行代碼 move(n-1, a, c, b), 就表示剩下的n-1個盤子是從a到b的. 剩下的代碼類似.

以下內容整理自網路上的博文：

遞歸思想不要糾結於過程。參照於"把大象關進冰箱需要幾步？"的思想，去解決漢羅塔問題。首先漢羅塔的三根柱子我命名為src（起始柱）、tmp（臨時柱）、dst（目的柱）：第一種情況：src上只有一個盤子的時候，src--&>dst；第二種情況：src上有一個以上的盤子（n個），分為三步解決。

把src從上到下的n-1個盤子藉助tmp移動到dst；
把src第n個盤子移動到dst；
把tmp上的n-1個盤子藉助src移動到dst。 不必在意中間細節

def move(n, src, tmp, dst): if n == 1: print("{} --&> {}".format(src, dst)) else: move(n-1, src, dst, tmp) print("{} --&> {}".format(src, dst)) move(n-1, tmp, src, dst)

n = int(input("please input a number for n: ")) move(n, "a", "b", "c")

這是在Edx上看到的程序：

def printMove(fr,to): print("move from "+str(fr)+" to "+str(to))


def Towers(n,fr="P1",to="P3",spare="P2"):

    if n==1:

        printMove(fr,to)

else: Towers(n-1,fr,spare,to) Towers(1,fr,to,spare) Towers(n-1,spare,to,fr)

從最大的問題開始，以三叉樹的形式不斷延展，最終產生n層問題，3^(n-1)個最底層問題（n=1)，其中每三個對應一個（n=2）問題，關係以此類推至最高層。每層一組的三個問題運行成功後，返回至上一層對應的問題的，像消消樂）逃一樣，但由於每一步中派生的三個步驟運行有先後，所以最底層的3^(n-1)個問題必然是從上（時間順序最前）到下引用 printMove函數，如：（X為某一個桿）

可以移步如何理解漢諾塔遞歸？這個問題@YIHE陳的回答很清晰。

N個盤子從小到大排a1-aN(N=1,2,3...)我們需要發現的一點是當前A和B上最大的盤子在C的最低部時，aN相當於不存在，因為A和B任意的搬動在C上都不會存在大盤在小盤上的情況，這是迭代的核心，此時問題就是N-1了。它是如何把aN先從A移到C呢，那三行代碼講的是先把前N-1個移到B上，再把A上剩的aN移到C，最後通過把A當臨時柱再把B上N-1個移到C上。函數內的迭代意思是每次在move（N-1）成立的情況下我先把N-1個當成目標，這時候相當於B是目標柱，C是臨時柱，再把aN移到C上，此時B是起始柱，而A是臨時柱了，我們又用move（N-1）完成相同的事，當然move（N-1）成立的情況是可以完成move(N-2),每次消去一個最大的，迭代就開始了。

move(4,"A","B","C")

if下面3個遞歸分別為1,2,3

知乎不支持空格？

這個代碼比我學那個好理解！

高階問題→一階問題→次階問題，傳遞迴歸。

現在我不懂的是輸出那些移動方案的原理，樓主大神get後幫忙解答一下！