Edison.X. Blog

這問題也有人譯為漢諾塔。這是由一個法國數學家 - 愛德華.盧卡斯 所提出之問題。印度某寺廟裡有三根柱子，其中一根有64個金盤，寺院裡的僧侶依照一個古老的預言之規則(規則稍後說明)去移動金盤；同時預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。

至於後期為何叫河內塔？事實上這傳說的變種已經愈來愈多，人物、時間、地點都有變過，而其中一個版本的地點就是越南的河內。接著說明河內塔的遊戲規則。

在一柱上有N個從小到大排好的盤子
(1) 請把這柱從小到大的盤子挪到另一柱子上。
(2) 移動過程中，只能小盤子放在大盤子上，不能大盤子放在小盤子上。

規則如上所示，為簡化問題，我們先假設只有2盤(小的是1，大的是2)，要把最Src那柱的盤子，全都挪到中間Des的柱子，只有一個Tmp柱子可做輔助，在移動過程，必須遵守上述規則。步驟與附圖如下所示：

step1：將第1盤從 SRC 柱放到 TMP 柱。
step2：將第2盤從 SRC 柱放到 DES 柱。
step3：將第1盤從 TMP 柱放回 DES 柱。

上述的這個步驟，可視為完成前 2 盤之步驟，若要完成前 N 盤的話：

step1：將第 n-1 盤從 SRC 柱放到 TMP 柱。
step2：將第 n    盤從 SRC 柱放到 DES 柱。
step3：將第 n-1 盤從 TMP 柱放回 DES 柱。

規則如上所示，原始碼如下所示，最後會顯示出步驟。

原始碼

#include <iostream>
using namespace std;

void HanoiTower(int no, char src, char des, char tmp)
{
        if(no!=0){
                HanoiTower(no-1, src, tmp, des);
                cout << "move no." << no << " plate from " << src << " to " << des << endl;
                HanoiTower(no-1, tmp, des, src);
        }
}
int main()
{
        // 4 盤為例, 從 A 搬到 C
        HanoiTower(4, 'A', 'C', 'B');
        return 0;
}

執行結果

move no. 1 plate from A to B
move no. 2 plate from A to C
move no. 1 plate from B to C
move no. 3 plate from A to B
move no. 1 plate from C to A
move no. 2 plate from C to B
move no. 1 plate from A to B
move no. 4 plate from A to C
move no. 1 plate from B to C
move no. 2 plate from B to A
move no. 1 plate from C to A
move no. 3 plate from B to C
move no. 1 plate from A to B
move no. 2 plate from A to C
move no. 1 plate from B to C