河內塔有 n 個圓盤時,把塔移到另一根柱子的最少步數是 2ⁿ−1 次。也就是把 2 連乘圓盤個數那麼多次,再減 1 的數。
| 圓盤個數 | 最少步數 |
|---|---|
| 1 個 | 1 次 |
| 2 個 | 3 次 |
| 3 個 | 7 次 |
| 4 個 | 15 次 |
| 5 個 | 31 次 |
| 6 個 | 63 次 |
| 7 個 | 127 次 |
| 8 個 | 255 次 |
| 9 個 | 511 次 |
圓盤每多 1 個,步數大約就變成 2 倍。我們依序來看看為什麼會這樣。
注意最大的圓盤
來想想把 n 個圓盤的塔從左邊移到右邊。最大的圓盤在其他圓盤的下面,所以直接是動不了的。要把最大的圓盤搬到右側,在那一瞬間必須是下面的狀態。
- 最大圓盤的上面,什麼都沒有放。
- 右側的柱子是空的(因為比最大圓盤小的圓盤,不能放在它下面)。
也就是說,剩下的 n−1 個圓盤,必須全部疊在中間的柱子上。
把步數分成 3 個部分
這樣一來,移動 n 個圓盤的步驟,可以分成下面 3 個部分。
- 把上面的 n−1 個圓盤,從左邊移到中間。
- 把最大的圓盤,從左邊一次移到右邊。
- 把中間的 n−1 個圓盤,移到大圓盤的上面。
1 和 3 都正好是「移動 n−1 個圓盤的塔」的問題。把 n 個圓盤的最少步數寫成 T(n),就會得到
T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1
這樣的關係。1 個圓盤時是 1 次,所以 T(1) = 1。由此依序可以求出 3、7、15、31……。
算式變成 2ⁿ−1 的原因
在這個關係的兩邊都加上 1,就會變成
T(n) + 1 = 2 × (T(n−1) + 1)
也就是說,「步數加 1 的數」,每多 1 個圓盤就剛好變成 2 倍。1 個圓盤時 T(1) + 1 = 2,所以 n 個圓盤時就是 2 連乘 n 次的 2ⁿ。再減掉 1,就得到 T(n) = 2ⁿ−1。
為什麼不可能更少
用上面的步驟可以用 2ⁿ−1 次移完,這點我們已經知道了。那麼,有沒有用更少步數移動的方法呢?
如同剛才所說,第一次移動最大圓盤的瞬間,剩下的 n−1 個圓盤必須全部疊在另一根柱子上。到那之前,至少需要移動 n−1 個圓盤的塔所需的步數。同樣地,最後把最大的圓盤放到右側之後,要把剩下的 n−1 個圓盤重新疊到它的上面,至少也需要移動 n−1 個圓盤的塔所需的步數。最大的圓盤本身,也至少要移動 1 次。
不論是什麼走法,這 3 個部分的步數一定都會用到。所以,不可能比 2 × T(n−1) + 1 次更少。其實也已經知道,最少步數的走法只有這 1 種。
App 的「經典」模式是 127 步
App「河內塔」的經典模式是 7 個圓盤,所以最少步數是 2⁷−1 = 127 步。步數剛好是 127,就表示是用最少步數解開的。照著玩法文章介紹的「把小圓盤朝同一個方向循環移動」的走法,就能剛好用 127 步完成。
