母牛的故事：C 語言實作費波那契數列變體解析

問題背景

這是一個經典的程式設計練習題，模擬母牛生育週期。假設母牛從第 4 年開始每年產一頭小母牛，而小母牛長到第 4 年也開始生育。給定年份 year，求該年份的母牛總數。這本質上是一個遞迴序列：f(n) = f(n-1) + f(n-3)，前四項分別為 1, 2, 3, 4。

核心演算法

程式採用動態規劃（DP）的思想，利用陣列 a[1000] 儲存每年的母牛數量，避免遞迴的重複計算。輸入以 0 結束，支援多組測試資料。

關鍵程式碼片段

#include <stdio.h>

int main() {
    int year, i;
    int a[1000];

    while (scanf("%d", &year) != EOF && year != 0) {
        a[0] = 1; // 第 1 年
        a[1] = 2; // 第 2 年
        a[2] = 3; // 第 3 年
        a[3] = 4; // 第 4 年

        for (i = 4; i < year; i++) {
            a[i] = a[i-1] + a[i-3];
        }

        printf("%d\n", a[year-1]);
    }
    return 0;
}

複雜度分析

• 時間複雜度： O(year) 每筆測資
• 空間複雜度： O(1000) 固定陣列

常見陷阱

注意陣列索引與年份的對應關係：a[year-1] 才是第 year 年的結果。另外輸入結束條件為 year != 0，不可漏寫。

延伸思考

若年份極大（如 10^9），可改用矩陣快速冪將時間降至 O(log n)。本題資料範圍較小，DP 解法足夠。