普考申論題
106年
[資訊處理] 程式設計概要
第 三 題
三、用 C 語言撰寫反覆結構（for-loop）及遞迴（recursive）2 個版本的函式，分別計算出費式數列（Fibonacci Sequence）：int F(int n)，其數學定義如下：
F0 = 0, F1 = 1, and Fn = Fn–1 + Fn–2 for n >1。（25 分）
例如: 呼叫 F(6) 計算出 8 and F(7) 計算出 13。
F0 = 0, F1 = 1, and Fn = Fn–1 + Fn–2 for n >1。（25 分）
例如: 呼叫 F(6) 計算出 8 and F(7) 計算出 13。
📝 此題為申論題
思路引導 VIP
看到費氏數列，應首先確立初始條件（F0=0, F1=1）與遞迴關係式（Fn=Fn-1+Fn-2）。遞迴版可直接將數學定義轉譯為程式碼；而反覆結構（for-loop）版則需利用變數滾動記錄前兩項的值，以迴圈逐步推導，避免遞迴造成的重複計算與效能低落。
🤖
AI 詳解
AI 專屬家教
【破題】 計算費氏數列的核心在於處理初始條件與狀態轉移。實作可分為直觀對應數學定義的「遞迴法」，以及具備較佳執行效能的「反覆結構（迴圈）法」。 【論述】
▼ 還有更多解析內容
費氏數列演算法實作
💡 掌握遞迴與迴圈處理重疊子問題的效能與實作差異。
| 比較維度 | 遞迴版本 (Recursive) | VS | 反覆版本 (Iterative) |
|---|---|---|---|
| 實作邏輯 | 由上而下呼叫自身 | — | 由下而上迴圈累加 |
| 時間複雜度 | 指數級 O(2^n) | — | 線性級 O(n) |
| 空間複雜度 | 需堆疊空間 O(n) | — | 常數空間 O(1) |
| 優缺點 | 代碼簡潔/重複運算 | — | 效能優異/代碼稍繁 |
💬遞迴寫法直觀但效能差，大型運算時必須改採反覆結構或動態規劃。
