申論題

要實現這個函式，我們可以使用遞歸，但這會導致很多重複計算。為了提高效率，我們可以使用動態規劃（Dynamic Programming, DP）的方法來儲存先前計算的結果，從而避免重複計算。這樣做可以將時間複雜度降到O(n)。

以下是根據給定規則實現fun函式的代碼，這個函式計算給定的數列f(n)的值：

c
Copy code
#include <stdio.h>

int fun(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 3;
    if (n == 4) return 5;
    
    int dp[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 5;

    for (int i = 5; i <= n; i++) {
        dp[i] = 3 * dp[i - 1] + 5 * dp[i - 3];
    }

    return dp[n];
}

int main() {
    int n;
    printf("Enter a positive integer n: ");
    scanf("%d", &n);
    
    printf("f(%d) = %d\n", n, fun(n));
    return 0;
}
這段代碼首先處理基本情況（即f(1)到f(4)的值），然後對於n > 4的情況，使用一個陣列dp來記錄每個f(i)的值，從i = 5開始迭代計算直到n。每一步計算都利用了先前計算的結果，從而避免了重複計算。

Big-O 分析
時間複雜度：由於我們對於從5到n的每個數字僅執行了一次計算，因此時間複雜度是O(n)。

空間複雜度：我們使用了一個額外的陣列dp來儲存從f(1)到f(n)的計算結果，因此空間複雜度也是O(n)。

總結來說，這個動態規劃方法使得我們在計算f(n)時，時間和空間複雜度都是線性的。