這個遊戲乍看起來有點複雜,其實解法相當簡單(為了方便起見,我們分別將三根桿子標記成 A, B, C,且都是將圓盤由 A 桿移向 C 桿)。
假設現在 A 桿上有 1 個圓盤,則直接將之移到 C 桿上。若是有 A 桿上有兩個圓盤,則先將第 1 個(最小的)圓盤移到 B 桿上,再將 A 桿剩下的第 2 個圓盤移到 C 桿上,最後將剛剛移到 B 桿上的第 1 個圓盤移到 C 桿第 2 個圓盤之上即可。
若是 3 個圓盤的情況呢?這時我們需要先忽略第 3 個圓盤,先把前 2 個圓盤以上述的方式移到 B 桿,再將第 3 個圓桿移到 C 桿之後,最後將 B 桿上的 2 個圓盤循同樣的方式移到 C 桿第 3 個圓盤之上即可。
所以同樣的,若是 4 個圓盤,就將前 3 層以一樣的方式移到 B 桿,再將第 4 個圓盤移到 C 桿上,最後再把 B 桿上的圓盤全部移到 C 桿上。
至於更多圓盤的情況,其實也都是運用這種規律解開。以下是 3 層與 4 層河內塔的最少移動解法圖例:
而這種河內塔解法,其實就類似程式的遞迴(recursion)。
怎麼說呢?假設現在你需要將一個 N 層河內塔由 A 桿移到 C 桿。依照上面的解法,我們需要先將前 N - 1 層的圓盤先移到 B 桿,再將第 N 層的圓盤移到 C 桿,最後將 B 桿上的圓盤全部移到 C 桿。
而要怎麼將前 N - 1 層的圓盤由 A 桿移到 B 桿呢?也是運用同樣的方式:將前 N - 2 層的圓盤先移到 A 桿,再將第 N 層的圓盤移到 B 桿,最後將 A 桿上的圓盤全部移到 B 桿。
就這樣下去,直到變成最簡易的移動 1 層圓盤為止。也就是說,遞迴的終止條件為移動的圓盤數 n = 1。
以下是解河內塔謎題的虛擬碼:
void Hanoi(Index n, char A, char B, char C) { if (n = 1) { print "將第" n "個圓盤由" A "移到" C; } else { Hanoi(n - 1, A, C, B); print "將第" n "個圓盤由" A "移到" C; Hanoi(n - 1, B, A, C); } }
最後,附上 C 語言的程式實作:
#include <stdio.h> #include <stdlib.h> void hanoi(int, char, char, char); int time = 0; int main(void) { int n; printf("請輸入河內塔的高度:"); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); printf("移動 %d 層河內塔共需移動 %d 次\n", n, time); system("pause"); } 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); printf("%d: 將第 %d 個圓盤由 %c 移到 %c\n", ++time, n, A, C); hanoi(n - 1, B, A, C); } }
小小的補充一下,假如用以上的程式去試看看,可以發現 N 層河內塔的最小移動次數恰好是 2n - 1。
2 回覆:
想請問你如果是雙色河內塔的解法是??
雙色河內塔他不會啦 過了快5年還答不出來 笑死
張貼留言