台綜大B30 計概114 第八題 解答 ※ 販售必究 ※ 台灣綜合大學; 資訊管理系; 轉學考

 Q8. MyFibo 數列定義為 f₀ = 1, f₁ = 2, f₂ = 3, 且 fₖ = fₖ₋₁ + fₖ₋₂ + fₖ₋₃ (k ≥ 2)。請分別寫出該數列的遞迴與迭代演算法（以虛擬碼或 C/C#/Java 語法撰寫）。

Ans:

好的，我幫你整理 MyFibo 數列 的 遞迴 與 迭代 演算法。

定義：

• f₀ = 1

• f₁ = 2

• f₂ = 3

• fₖ = fₖ₋₁ + fₖ₋₂ + fₖ₋₃, for k ≥ 3

---

遞迴演算法 (Recursive)

偽代碼 / C-like 語法

int MyFibo(int k) {
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) return 3;
    return MyFibo(k - 1) + MyFibo(k - 2) + MyFibo(k - 3);
}

---

迭代演算法 (Iterative)

偽代碼 / C-like 語法

int MyFiboIter(int k) {
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) return 3;

    int f0 = 1, f1 = 2, f2 = 3;
    int f = 0;

    for (int i = 3; i <= k; i++) {
        f = f0 + f1 + f2;
        // shift window
        f0 = f1;
        f1 = f2;
        f2 = f;
    }

    return f;
}

---

👉 範例：計算前幾項

• f₀ = 1

• f₁ = 2

• f₂ = 3

• f₃ = 1 + 2 + 3 = 6

• f₄ = 2 + 3 + 6 = 11

• f₅ = 3 + 6 + 11 = 20

所以序列開頭是： 1, 2, 3, 6, 11, 20, …