C++ 母牛問題：遞迴與迭代兩種解法完整解析

經典遞迴題目：「一頭母牛，出生第 4 年起每年生一頭母牛，第 n 年共有多少頭？」這是斐波那契變體，遞推關係為：

f(1)=f(2)=f(3)=1
f(n) = f(n-1) + f(n-3)   (n > 3)

因為第 n 年的牛 = 上一年所有牛 (f(n-1)) + 新出生的牛 (第 n-3 年已存在的牛，今年生育)。

遞迴解法 (教學用，效能差)

long long cowRec(int n) {
    if (n <= 3) return 1;
    return cowRec(n-1) + cowRec(n-3);  // 指數級複雜度，n>40 明顯卡頓
}

迭代解法 (O(n) 時間、O(1) 空間，推薦)

long long cowIter(int n) {
    if (n <= 3) return 1;
    long long a = 1, b = 1, c = 1; // f(n-3), f(n-2), f(n-1)
    for (int i = 4; i <= n; ++i) {
        long long cur = c + a;       // f(n) = f(n-1) + f(n-3)
        a = b;
        b = c;
        c = cur;
    }
    return c;
}

矩陣快速冪優化 (O(log n)，超大 n 才需用)

// 狀態向量 [f(n), f(n-1), f(n-2)]^T
// 轉移矩陣 [[1,0,1],[1,0,0],[0,1,0]]
// 矩陣快速冪略

測試主程式

int main() {
    for (int n = 1; n <= 20; ++n)
        printf("Year %2d: %lld\n", n, cowIter(n));
    return 0;
}
/* 輸出
Year  1: 1
Year  2: 1
Year  3: 1
Year  4: 2
Year  5: 3
Year  6: 4
Year  7: 6
Year  8: 9
Year  9: 13
Year 10: 19
...
*/

常見誤區

• 以為「每 4 年翻倍」 → 錯。是 f(n)=f(n-1)+f(n-3)，非翻倍。
• 遞迴未加備忘錄 → 重複計算爆炸。
• int 溢位 → n=50 時超過 21 億，必須用 long long 或 BigInteger。

掌握遞推關係 → 寫迭代 → 注意資料型別，這題就能穩拿滿分。