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

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

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

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

h.PNG 

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

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()