Tower of Hanoi

Tower of Hanoi(河內塔)
前幾日在練習C Language的遞迴時候，,裡頭的一小題，看了好久最後才懂得它的運作原理，簡單介紹一下它背景，

最早發明這個問題的人是法國 數學家愛德華·盧卡斯，傳說中在印度某間寺院有三根柱子，上串64個金盤。依規定在每次只能搬移一片金盤至另一根柱子，且在過程中必須保持金盤由上至下是直徑由小至大的順序，意指任何一根柱子上，金盤都是直徑較小的被放在上層。預言說當這些盤子移動完畢，世界就會滅亡。也有人說這故事是盧卡斯自創，其真實性就不得而知了。若有興趣的人可以去網路上找尋相關資料，這裡就不再額外敘述了。

　　這裡就用簡單的3個金盤作例子介紹，如上頭之動畫圖所示，假設有3支柱子分別為A, B, C，3金盤分別d1, d2, d3 (半徑 d1< d2 < d3)

(0)初始結構
A: d3, d2, d1
B:
C:

(1)將d1由A移至C
A: d3, d2
B:
C: d1

(2)將d2由A移至B
A: d3
B: d2
C: d1

(3)將d1由C移至B
A: d3
B: d2, d1
C:

(4)將d3由A移至C
A:
B: d2, d1
C: d3

(5)將d1由B移至A
A: d1
B: d2
C: d3
2, d1
(6)將d2由B移至C
A: d1
B:
C: d3, d2
1
(7)將d1由A移至C，結束
A:
B:
C: d3, d2, d1

這裡不細說內部的流程步驟，只用簡單規則來說明。因為大半徑的金盤須放置目的柱最底層，故以此小範例作解釋，如果要把d3從A柱(出發柱)放置C柱(目的柱)，那必須把本來在A柱中d3以上的金盤(d2, d1)想辦法移置B柱(緩衝柱) [參考第(4)步驟]，這樣才有辦法把d3由A柱直接移置C柱。等到移完d3，就必須再把原來B柱中的金盤全部移到C柱 [參考第(6)步驟]。

故可以歸納出一簡單的規則，若要移動第n個金盤，須依序考慮以下三大步驟，
(1) 先把第1~n-1個金盤從出發柱移到緩衝柱
(2) 把第n個金盤從出發柱移到目的柱
(3) 再把第1~n-1個金盤從緩衝柱移到目的柱

將上述三大步驟利用遞迴的方式，就可求解出在n個金盤下要如何在3支柱子上作移動。程式碼如下，
#include < stdio.h >
#include < stdlib.h >

void hanoi(int t, char A, char B, char C); //宣告一個河內塔公式，第一個變數為計數器，第二個變數為出發柱，第三個變數為緩衝柱，第四個變數為目的柱
int time = 0;

int main(void)
{
int n;
printf("請輸入金盤數：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
printf("移動 %d 層金盤共需移動 %d 次\n", n, time);
return 0;
}

void hanoi(int n, char A, char B, char C)
{
if (n == 1)
{
printf("%d: 將第 %d 個金盤由 %c 移到 %c\n", time++, n, A, C); //當只有一個金盤就直接從出發柱移到目的柱
}
else
{
hanoi(n - 1, A, C, B); //把第1~n-1個金盤從出發柱移到緩衝柱
printf("%d: 將第 %d 個金盤由 %c 移到 %c\n", time++, n, A, C); 把第n個金盤從出發柱移到目的柱
hanoi(n - 1, B, A, C); //把第1~n-1個金盤從緩衝柱移到目的柱
}
}

以上之是考慮用遞迴方式去作計算，建議可以使用debug模式去追蹤hanoiy函數，這樣你就可以了解整個運算過程。