moea_joint_essay 111年 [資訊] 資訊管理、程式設計

第三題

📖 題組：
有一費氏(Fibonacci)數學函式如下：（3 題，每題 5 分，共 15 分） F(n) = F(n – 1) + F(n – 2)，n > 0 F(1) = 1、F(0) = 0

📝 此題為申論題，共 3 小題

小題 (三)

為避免因為遞迴呼叫浪費函式重複計算的時間，試修改(一)中的程式碼，仍須使用遞迴的方式，使其計算時不須重複計算 F(n – 1)和 F(n – 2)函式。

可使用記憶化 (Memoization) 技巧儲存已經計算過的結果，或使用尾遞迴 (Tail Recursion) 攜帶中間結果。

🤖

AI 詳解

AI 專屬家教

以下示範使用「尾遞迴(Tail Recursion)」方式，將狀態值透過參數傳遞，以達成不再重複計算的分支，且仍保有遞迴特性：

# a 代表 F(0) 或前一狀態，b 代表 F(1) 或當前狀態

請以遞迴(Recursive)方式寫出上列函式程式碼。

直接根據數學定義，將 f(0) 與 f(1) 當作遞迴終止條件，並回傳遞迴呼叫相加的結果。

🤖

AI 詳解

AI 專屬家教

以下使用 Python 撰寫（亦可視為泛用虛擬碼）：

def fibonacci_recursive(n):

請以非遞迴(Non- Recursive)方式寫出上列函式程式碼。

使用迴圈(迭代法)，保留前兩個數字的狀態累加到當前項目，避免函式重複呼叫。

🤖

AI 詳解

AI 專屬家教

以下使用 Python 撰寫（迭代方式）：

def fibonacci_iterative(n):

查看更多「[資訊] 資訊管理、程式設計」的主題分類考古題