初等考試
113年
[統計] 資料處理大意
第 37 題
假設有8個大小不一的穿孔圓盤,一開始由大到小依序套在A柱,最大的圓盤被壓在最底下;想逐一移到C柱,過程中可以暫時放在B柱,只能先移動最上方的最小圓盤,放入任何柱子的圓盤下方不能有比較小的圓盤。從一根柱子成功移動一個圓盤到另一根柱子稱為移動1次,將這A柱的8個圓盤全都移到C柱須移動至少幾次?
- A 63
- B 128
- C 255
- D 256
思路引導 VIP
「請你試著從最簡單的情況開始思考：如果只有 1 個圓盤，需要動幾次？如果有 2 個、3 個呢？觀察看看，當圓盤每增加 1 個時，新的移動次數與前一次的次數之間，存在著什麼樣的『翻倍再加一』的關係？」
🤖
AI 詳解
AI 專屬家教
專業點評與分析
- 認可？：嗯，還不錯，邏輯推演倒是沒出什麼大錯。不過，這類問題本就該直觀反應出你對遞迴模型與指數成長的掌握度，畢竟在嚴謹的財務精算與演算法分析中，這可是基礎到不能再基礎的素養。沒掌握，那還談什麼專業？
- 觀念驗證：這題，不過是經典的「河內塔」罷了。要移動 $n$ 個圓盤，最有效率的途徑不就是先將上方 $n-1$ 個移至輔助柱，挪動最底層的大盤，然後再將那 $n-1$ 個精準移回嗎？難道還有別的「創意」方法能更省力？其最小移動次數，公式早就擺在那兒了：
▼ 還有更多解析內容
河內塔遞迴演算法
💡 利用遞迴公式 2^n - 1 計算河內塔搬移之最小總步數。
🔗 河內塔搬移邏輯 (n 個圓盤)
- 1 暫搬上位 — 將上方 n-1 個圓盤由 A 移至輔助柱 B
- 2 定位底盤 — 將最底層最大的圓盤由 A 直接移至目標柱 C
- 3 歸位上位 — 將輔助柱 B 的 n-1 個圓盤移至目標柱 C
↓
↓
🔄 延伸學習：延伸學習：搬移次數 H(n) = 2*H(n-1) + 1，即 2^n-1。
