地特四等申論題
107年
[資訊處理] 程式設計概要
第 一 題
📖 題組：
給定X()函數的數學定義如下:(每小題10分,共30分) X(0)=1, X(1)=1, X(2)=1, X(k+1)=X(k-2)+X(k-1)+X (k)
給定X()函數的數學定義如下:(每小題10分,共30分) X(0)=1, X(1)=1, X(2)=1, X(k+1)=X(k-2)+X(k-1)+X (k)
📝 此題為申論題，共 3 小題
小題 (一)
請完成下列的遞迴函式,用以計算並回傳X(i)的值。
int X1 (int k) {
if ( _____ )
return _____ ;
else
return ( _____ );
}
思路引導 VIP
解此題首先要掌握遞迴函式的兩大核心要素：終止條件（Base case）與遞迴關係式（Recursive step）。觀察題目給定的數學定義，找出基本條件的值以填補 if 區塊；接著將 X(k+1) 的關係式進行變數平移代換，求出 X(k) 的通式，即可順利填寫 else 的遞迴呼叫區塊。
小題 (二)
請用六行以內的程式碼完成下列的for-迴圈函式,用以計算並回傳X(i)的值。
int X2 (int k) {
int S1=1, S2=1, S3=1, sum = 0; // sum 為需要回傳的值
if (k > 3)
for ( _____ ) { ... }
return sum;
}
思路引導 VIP
此題考查將遞迴數列轉換為迭代（迴圈）形式的「狀態保留」技巧。看到此題應先確認 X(k) 與前三項的遞迴關係，並利用三個已知變數（S1, S2, S3）在迴圈中進行「滾動更新」，從已知基礎逐步推導出目標值。
小題 (三)
上述兩個不同函式,請說明何者執行上會比較有效率。
思路引導 VIP
看到此類遞迴數學定義的實作比較題，應立即聯想到「純遞迴 (Recursion)」與「迴圈/動態規劃 (Iteration/DP)」兩種常見解法。解題關鍵在於切入分析『時間複雜度（是否產生大量重疊子問題）』與『空間複雜度（記憶體呼叫堆疊的開銷）』來判定執行效率高低。