河內之塔(Towers of Hanoi)
是法國人M.Claus(Lucas)1883年從泰國帶至法國的,

河內為越戰時北越的首都,
即現在的胡志明市;
1883
年法國數學家 Edouard Lucas曾提及這個故事,
據說創世紀時Benares有一座波羅教塔,
是由三支鑽石棒(Pag)所支撐,
開始時神在第一根棒上放置64個由上至下依由小 至大排列的金盤(Disc),
並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,
且搬運過程中遵守大盤子在小盤子之下的原則,
若每日僅搬一個盤子,則當 盤子全數搬運完畢之時,
此塔將毀損,
而也就是世界末日來臨之時。
解答:最少需移動264-1次


 264= 18,446,744,073,709,551,616
64
個圓盤如果一秒搬一個的話

最快需要264 -1 秒才能搬完  5845.54億年‧‧‧(維基百科,自由的百科全書的估算http://zh.wikipedia.org/zh-hk/%E6%B2%B3%E5%85%A7%E5%A1%94)


 



下列網站可自己操作:http://www.mathland.idv.tw/game/hanoi/hanoi.htm


河內塔教學.mpg






河內塔



相信許多人都有玩過河內塔『Tower of Hanoi』的經驗,在不斷搬移的過程中,必須遵循著一定的遊戲規則:上方的環一定要比下方的小,且一次只能搬動一個環。

但是否我們只能不斷嘗試、碰運氣,最後幸運地搬完所有的環?還是說,有其他的規律可循 ?

以下是自己在玩過河內塔後歸納出的規律


若環共有3個,將環由小至大編號1.2.3,則



  1. 1號環移到第3根柱上,
  2. 2號環移至中間的柱子,
  3. 1號環移到2號環之上<也就是移到中間的柱子>
  4. 3號環移到第3根柱子<也就是目標柱>
  5. 1號環移至第一根柱子,
  6. 2號環移至目標柱,
  7. 1號環移至目標柱即完成。

7次是完成3環的河內塔所需最少的移動次數。

若環共有4個,將其由小至大編號為1.2.3.4,則



  1. 1號環移到中間的柱子,
  2. 2號環移到第3根柱子,
  3. 1號環移到2號環上<也就是第3根柱子>
  4. 3號環移到中間的柱子,
  5. 1號環移到4號環上也就是第一根柱子>
  6. 2號環移到3號環上<中間的柱子>
  7. 1號環移至中間的柱子,
  8. 4號環移至目標柱<3根柱子>
  9. 1號環移至第3根柱子,
  10. 2號環移至第1根柱子,
  11. 1號環移至2號環上<也就是第1根柱子>
  12. 3號環移至4號環上<目標柱上>
  13. 1號環移至中間柱,
  14. 2號環移至目標柱,
  15. 1號環移至目標柱即完成。

15次是完成4環河內塔所需最少次數。

因此我們可以歸納出下列公式 :



  • 環數n=3時,所需最小移動次數x20+21+22=1+2+4=7
  • 環數n=4時,所需最小移動次數x20+21+22+23=1+2+4+8=15
  • 環數n=N時,所需最小移動次數x
                 20+21+22+23+......=1+2+4+8+......+2(N-1)=Σ2(n-1)

  • 如取N=64,最少需移動264-1次

其中,20=1為所有環中最大環的總移動次數,以此類推,2n-1即為所有環中最小環的總移動次數。


 轉貼自:http://www.psy.kmu.edu.tw/~choco/Hanoi.html


深入研究http://teach.ymhs.tyc.edu.tw/t1086/study/knowle/Hanoi-tower.htm


arrow
arrow
    全站熱搜

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