河內塔

相信許多人都有玩過河內塔『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環河內塔所需最少次數。

因此我們可以歸納出下列公式 :
其中,20=1為所有環中最大環的總移動次數,以此類推,2n-1即為所有環中最小環的總移動次數。

首頁