河內之塔(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號環移到第3根柱上，
- 將2號環移至中間的柱子，
- 將1號環移到2號環之上<也就是移到中間的柱子>，
- 將3號環移到第3根柱子<也就是目標柱>，
- 將1號環移至第一根柱子，
- 將2號環移至目標柱，
- 將1號環移至目標柱即完成。
7次是完成3環的河內塔所需最少的移動次數。
若環共有4個，將其由小至大編號為1.2.3.4，則
- 將1號環移到中間的柱子，
- 將2號環移到第3根柱子，
- 將1號環移到2號環上<也就是第3根柱子>，
- 將3號環移到中間的柱子，
- 將1號環移到4號環上也就是第一根柱子>，
- 將2號環移到3號環上<中間的柱子>，
- 將1號環移至中間的柱子，
- 將4號環移至目標柱<第3根柱子>，
- 將1號環移至第3根柱子，
- 將2號環移至第1根柱子，
- 將1號環移至2號環上<也就是第1根柱子>，
- 將3號環移至4號環上<目標柱上>，
- 將1號環移至中間柱，
- 將2號環移至目標柱，
- 將1號環移至目標柱即完成。
15次是完成4環河內塔所需最少次數。
因此我們可以歸納出下列公式 ：
- 環數n=3時，所需最小移動次數x：20+21+22=1+2+4=7；
- 環數n=4時，所需最小移動次數x：20+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
留言列表
