Tower of Hanoi

漢諾塔怎麼玩

漢諾塔是經典的遞迴益智遊戲。所有圓盤一開始由大到小、最大的在最下面，全部疊在左邊的柱子上。你要把整疊圓盤搬到右邊的柱子，一次只能搬一個，並遵守兩條規則：每次只能搬動某根柱子最上面的圓盤，而且永遠不能把大的圓盤疊在小的上面。點一根柱子拿起它最上面的圓盤，再點另一根柱子把它放下。目標是用最少的步數，在右邊的柱子重新疊好這座塔。

最少步數與 2^n−1 公式

解開 n 個圓盤的漢諾塔，所需的最少步數正好是 2ⁿ − 1。三個圓盤要 7 步，四個要 15 步，五個要 31 步。沒有任何走法能突破這個下限，所以排行榜上等於 2ⁿ − 1 的成績就是完美的最佳解。

遞迴解法策略

• 要把 n 個圓盤從來源柱搬到目標柱，先把最上面的 n − 1 個圓盤搬到備用（輔助）柱。
• 把最大的那個圓盤直接從來源柱搬到目標柱。
• 最後，把備用柱上的 n − 1 個圓盤搬到最大圓盤的上面。每一個子堆疊都用同樣的方法解，一路遞迴到只剩一個圓盤為止。

漢諾塔要怎麼用最少步數解？套用上面的遞迴：把問題拆成「先把 n−1 個移開、搬走最大的、再把 n−1 個移回來」。還有一個簡單的迭代技巧——每隔一步就把最小的圓盤朝同一個循環方向移動，中間再做唯一的另一個合法移動——同樣能重現最佳的 2ⁿ − 1 步序列。