母牛生育遞歸問題：C 語言實現與邏輯錯誤修正

杭電 2018 經典算法題：一頭母牛每年初生一頭小母牛，小母牛從第四個年頭開始每年初也生一頭。求第 n 年母牛總數。本文分析遞歸規律，指出原代碼邏輯錯誤並給出正確實現。

題目描述

• 輸入多組測試數據，每行一個整數 n (0 < n < 55)，n=0 結束。
• 輸出第 n 年母牛數量。
• 樣例：n=2 → 2；n=4 → 4；n=5 → 6。

原代碼邏輯缺陷

while(scanf("%d", &n) != EOF) {
    // ... 計算邏輯 ...
    printf("%d\n", sum);
}

問題：循環條件未判斷 n==0，導致輸入 0 時仍執行計算，且遞歸公式 a[t] = a[t-1] + a[t-3] 與數組求和邏輯不符合題意。

正確遞歸關係

設 f(n) 為第 n 年牛數：

• f(1)=1, f(2)=2, f(3)=3
• n≥4 時：f(n) = f(n-1) + f(n-3)
• 解釋：上一年所有牛存活 + 三年前出生的牛（今年開始生育）

修正後代碼

#include <stdio.h>

int main() {
    int n;
    long long f[55] = {0, 1, 2, 3}; // 索引即年份
    for (int i = 4; i < 55; ++i) {
        f[i] = f[i-1] + f[i-3];
    }
    while (scanf("%d", &n) == 1 && n != 0) {
        printf("%lld\n", f[n]);
    }
    return 0;
}

核心修正點

1. 循環條件改為 while (scanf("%d", &n) == 1 && n != 0)，遇 0 即停止。
2. 預先計算所有 f[n]，查表輸出，避免重複計算。
3. 使用 long long 防止溢出（n=54 時結果約 1.3 億）。