河內塔

2007/10/03

在Computer Science裏有一個很出名的問題,叫河內塔。故事裏說在某個古遠的東方國度裏,有個寺院裏有三根高高的柱,其中一根由上而下由小至大的串上六十四個圓形金盤,有一個和尚負責把金盤通通移到另一根柱子去,但規則是每次只準移動一個金盤,並且在任何時候都不可以把大的蓋在小的盤上。

故事說,一天,當和尚完成整個過程時,就是世界末日。

幸好,數學家証明了和尚起碼要移動2^64-1次,如果和尚手快,不眠不休,不吃不喝,一秒一個,大概五千八百億年就可以完成整個過程。相信五千八百億年內人類一定會發明更加快捷的自毁方法,所以,從此以後,河內塔只出現於課本裏。

一天跟印度同學談起這個問題,胡謅了很多無聊的解決方法,然後又談及這東西的典故,印度同學問我這是不是個中國的故事,我心想,吓!這不是印度的故事麼?我反問印度同學,他卻說在印度,人們都認為這是中國做的好事。真奇怪。

當然,幾經查証,wiki說這是個印度的故事。

廣告

5 回應 to “河內塔”

  1. C.M. Says:

    這個河内塔,最初出現小弟眼前的時候,大概是20年前,初中的時候,老父介紹的。那時我還以為叫 Pascal。或許當時電腦時代介紹用 Pascal解決吧。而我,也曾用各種硬幣於此塔偷閑過一陣子。

    記得的解決方法很簡單,若果硬幣/圈圈(i.e. 金盤)的數量為單數,那第一次移動(即最小的一個硬幣)便先要移到中間的位置(i.e.柱)。而第二大的硬幣便移到最後的位置(i.e. 柱),然後把最小的硬幣,移到最後的位置… 如此類推。若硬幣的數量為雙數,那便倒轉柱子的先後次序。

    緊記這個“單雙”的規則,便可以毫無困難地,以最少的次數移動所有硬幣。

    即是說,64個金盤的第一步,就是把最小的移到最後的柱子。

  2. C.M. Says:

    原來Wiki解釋得這麼詳細,害我變了白痴… 😦

  3. leona Says:

    這個故事/與印度的同學的閒扯好過癮!
    這就是大學生活美妙之處了。

  4. Justin Says:

    CM,但你都好勁喎,咁耐既事你都仲記得咁清楚。解決呢個問題既最重要既一個部份基本上就係你第二段講既野,就係將一個問題分為一些比較細小既問題,然之後解決左佢⋯⋯⋯⋯⋯

    你以前話你唔係好熟電腦,好明顯都唔係啫!!

    Leona: 對呀!跟同學胡扯永遠是件痛快的事。

  5. C.M. Says:

    哎吔!依家睇番,先見到64個金盤係雙數,第一步應該係放中間個圈圈。呵呵,我又一次丟人現眼囉…

    Justin,我依家真係唔熟電腦,但o係我地果個年代,都係玩Apple II 同basic 大。(未有Harddisk果時,我地用cassette機+帶黎run PC game 架)


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: