C語言遞歸數列：母牛生產問題（費波那契變體）

問題描述

母牛出生第 4 年開始每年生一頭小母牛，小母牛長大後同樣規則繁殖。第 1 年有 1 頭母牛，求第 n 年總母牛數。輸入多組 n，n=0 結束。

遞歸關係推導

• 第 1 年：1 頭（初始母牛）
• 第 2 年：2 頭（初始 + 1 歲）
• 第 3 年：3 頭（初始 + 2 歲 + 1 歲）
• 第 4 年：4 頭（初始產第 1 胎）
• 第 n 年（n≥4）：f(n) = f(n-1) + f(n-3)

解釋：第 n 年總數 = 第 n-1 年存活牛數 + 第 n-3 年出生的牛（今年剛好 3 歲，開始產仔）。

原始代碼分析

使用陣列 a[1000] 自底向上 DP 計算，正確。但陣列大小固定，若 n>1000 會越界。且每次查詢重新計算，可優化為預計算或備忘錄。

優化版：預計算 + 大數支援

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 大數加法（字串模擬），支援極大 n
void add_strings(char *res, const char *a, const char *b) {
    int i = strlen(a)-1, j = strlen(b)-1, k = 0, carry = 0;
    char tmp[2000];
    while (i>=0 || j>=0 || carry) {
        int da = (i>=0)? a[i]-'0':0;
        int db = (j>=0)? b[j]-'0':0;
        int sum = da + db + carry;
        tmp[k++] = '0' + (sum%10);
        carry = sum/10;
        i--; j--;
    }
    for (int x=0; x 1000) { puts("Exceeds precomputed limit"); continue; }
        printf("%s\n", cows[n-1]);
    }
    for (int i=0; i<=1000; i++) free(cows[i]);
    return 0;
}

關鍵點總結

1. 遞歸公式：f(n)=f(n-1)+f(n-3)，初始 f(1..4)={1,2,3,4}。
2. DP 自底向上：避免遞歸重複計算，時間 O(n)。
3. 大數處理：n=1000 時結果約 200 位，需高精度加法（或用 Python/Java BigInteger 驗證）。
4. 矩陣快速冪：若需極大 n（如 10⁹），可構造 3×3 矩陣 [[1,0,1],[1,0,0],[0,1,0]] 快速冪求解，O(log n)。

相關經典變體

• 兔子繁殖（費波那契 f(n)=f(n-1)+f(n-2)）。
• 青蛙跳台階（一次 1/2 級 → 費波那契；一次 1/2/3 級 → 三步遞歸）。
• 母牛問題若改為第 3 年產仔，公式變為 f(n)=f(n-1)+f(n-2) 即費波那契。