高考申論題
114年
[資訊處理] 資料結構
第 四 題
四、根據下列的虛擬碼，若 n = 21 則傳回的答案為何？請說明。其中 floor()為數學上的地板函數（floor function）。（20 分）
function splitSum(n: integer) returns integer
if n <= 1 then
return 1
a ← floor(n / 2)
b ← floor(n / 3)
return splitSum(a) + splitSum(b)
function splitSum(n: integer) returns integer
if n <= 1 then
return 1
a ← floor(n / 2)
b ← floor(n / 3)
return splitSum(a) + splitSum(b)
📝 此題為申論題
思路引導 VIP
遇到遞迴演算法追蹤題，應先找出「終止條件」與「遞迴關係式」。建議採用樹狀展開或由下而上（Bottom-up）的推導方式，將計算過的小問題結果記錄下來以避免重複計算，即可順利推導出最終結果。
🤖
AI 詳解
AI 專屬家教
【解題思路】利用遞迴關係展開與由下而上（Bottom-Up）的計算方式，逐步分解問題並代入基準條件（Base Case）求值。 【詳解】 已知：
▼ 還有更多解析內容
遞迴函式追蹤計算
💡 掌握遞迴基準條件與子問題展開，並系統性由下而上求值。
🔗 遞迴求解四步驟
- 1 標記基準點 — 找出 n <= 1 時函數傳回 1 的終止條件
- 2 拆解大問題 — 依公式將 S(21) 分解為 S(10) 與 S(7)
- 3 由底層遞算 — 由 S(0) 開始算出所有必要子問題並列表
- 4 回代得結果 — 將計算出的子項數值加總得出最後答案
↓
↓
↓
🔄 延伸學習：延伸學習：動態規劃中利用空間換取時間的 Memoization 優化技術
