Q8.
河內塔(Tower of Hanoi)問題中，欲搬動n 個套環，最少必須移動幾次？
電腦軟體設計共同科目 · 乙級 · Q8
難易度分析
2 / 5
本題考查經典遞迴演算法的數學公式，需能準確區分指數成長與多項式成長的差異，避免將其與常見的級數求和或平方項混淆。
正確答案：③
③ :2ⁿ - 1 為河內塔最小移動次數的遞迴解。推導方式：T(n) = 2·T(n-1) + 1，展開後即得 2ⁿ - 1。
:2ⁿ - 1 為河內塔最小移動次數的遞迴解。推導方式：T(n) = 2·T(n-1) + 1，展開後即得 2ⁿ - 1。錯誤選項解析
- ① n:線性複雜度 n 僅代表與套環數量成正比，但河內塔屬於指數型遞迴問題，實際移動次數遠大於 n。
- ② n(n+1)/2:n(n+1)/2 是等差級數求和公式（如氣泡排序比較次數），不適用於河內塔的遞迴關係式。
- ④
:n² 屬於多項式複雜度，但河內塔的本質是指數成長，兩者時間複雜度等級完全不同。
Learning Tip
"河內塔是遞迴與分治策略的經典考題，核心在於掌握 T(n) = 2ⁿ - 1 的推導過程。常考陷阱為將 2ⁿ - 1 與 n² 或 n(n+1)/2 混淆，需牢記此為指數時間複雜度 O(2ⁿ)，當 n 增大時移動次數會急遽增加。"
學員答題分佈
①n0%
②n(n+1)/20%
③0%
0%④0%
0%此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
