moea_joint_essay
111年
[統計資訊] 資料庫及資料探勘、程式設計
第 一 題
📖 題組：
有一費氏(Fibonacci)數學函式如下：（3 題，每題 5 分，共 15 分） F(n) = F(n – 1) + F(n – 2)，n > 0 F(1) = 1、F(0) = 0
有一費氏(Fibonacci)數學函式如下：（3 題，每題 5 分，共 15 分） F(n) = F(n – 1) + F(n – 2)，n > 0 F(1) = 1、F(0) = 0
📝 此題為申論題，共 3 小題
小題 (一)
請以遞迴(Recursive)方式寫出上列函式程式碼。
思路引導 VIP
寫出基本的遞迴函式，包含終止條件 (n=0, n=1) 與遞迴呼叫 (F(n-1)+F(n-2))。
小題 (二)
請以非遞迴(Non- Recursive)方式寫出上列函式程式碼。
思路引導 VIP
使用迴圈(Iteration)方式計算，設定兩個變數紀錄前兩項的值，逐步相加求得下一項。
小題 (三)
為避免因為遞迴呼叫浪費函式重複計算的時間，試修改(一)中的程式碼，仍須使用遞迴的方式，使其計算時不須重複計算 F(n – 1)和 F(n – 2)函式。
思路引導 VIP
採用動態規劃的「記憶化搜尋」(Memoization)，將已經計算過的值儲存在陣列中，如果陣列有值則直接返回，避免重複展開。
遞迴費氏數列實作
💡 將函數定義分解為基本條件與呼叫自身的規律公式。
- 確立終止條件防止無限遞迴（Base Case）
- 將數學公式轉化為回傳值的遞迴呼叫
- 確保輸入參數在呼叫後趨向終止條件
- 注意遞迴深度與重複計算造成的效能問題
