河內塔演算法的分析(Hanoi Algorithm Analysis)

它的演算法如下：

Procedure HANOI(n, A, B, C)

IF(n == 1)
    PRINT("Move sheet " n " from " A " to " C)
ELSE
    HANOI(n-1, A, C, B)
    HANOI(1, A, B, C)
    HANOI(n-1, B, A, C) 

#演算法引用至良葛格的網頁

接下來我們分析其呼叫流程：

假設我們有三個盤子，故n =3, method定義為HANOI(n, A, B, C)，需執行2^3-1 = 7步

由於自己呼叫自己，故進入HANOI(n, A, B, C)==>呼叫HANOI(n-1, A, C, B)

n=3-1, A(值) => A(M's參數), C(值) => B, B(值) => C (=>這邊可以想做帶入, M=>method)

由於自己呼叫自己，故進入HANOI(n, A, B, C)==>呼叫HANOI(n-1, A, C, B)

n =2-1, A => A, B => B, C => C

由於自己呼叫自己，故進入HANOI(n, A, B, C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=A, C=C，故會print Move sheet 1 from A to C---(1)

再來回到上一個呼叫的method繼續執行HANOI(1, A, B, C)，進入HANOI(n, A, B, C)

(請注意，藍色的(1, A, B, C)值，要以n=3-1帶入時為例，故B=C, C=B)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=A, C=B，故會print Move sheet 1 from A to B---(2)

再來繼續執行HANOI(n-1, B, A, C)，進入HANOI(n, A, B, C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=C, C=B，故會print Move sheet 1 from C to B---(3)

**************************藍色部分執行完畢**************************

再來回到上上一個呼叫的method繼續執行HANOI(1, A, B, C)，進入HANOI(n, A, B, C)

(請注意，橘色的(1, A, B, C)值需以n=3時為例，此時B=B, C=C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=A, C=C，故會print Move sheet 1 from A to C---(4)

再來繼續執行HANOI(n-1, B, A, C)(這裡的n = 3)

n =3, B => A, A => B, C => C

進入HANOI(n, A, B, C)(這裡的n = 2)

由於自己呼叫自己，故進入HANOI(n, A, B, C)==>呼叫HANOI(n-1, A, C, B)

n =2-1, B => A, C => B, A => C

由於自己呼叫自己，故再進入HANOI(n, A, B, C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=B, C=A，故會print Move sheet 1 from B to A---(5)

再來回到上一個呼叫的method繼續執行HANOI(1, A, B, C)(n=2,A,B,C的值由n=3帶入)

進入HANOI(n, A, B, C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=B, C=C，故會print Move sheet 1 from B to C---(6)

再來繼續執行HANOI(n-1, B, A, C)，進入HANOI(n, A, B, C)

但n=1，故IF成立，執行PRINT("Move sheet " n " from " A " to " C)

=>執行搬移，此時參數A=A, C=C，故會print Move sheet 1 from A to C---(7)

紫色部分執行完畢

再來回到執行HANOI(n-1, B, A, C)之後，由於以無可呼叫，各到此執行完畢！！

PS. 有點雜，此為小弟自行分析的執行流程，有問題請不吝指正 囧