Python 解決母牛繁殖問題：遞歸與迭代優化

問題建模

• 第 1 年初：1 頭母牛（成熟）
• 第 2 年初：2 頭（原牛 + 新生）
• 第 3 年初：3 頭
• 第 4 年初：4 頭（原牛第 4 年生，第 1 年生的牛尚未成熟）
• 第 n 年 (n≥5)：f(n) = f(n-1) + f(n-3)
  （上一年所有牛存活 + 三年前出生的牛開始生產）

遞歸實現（帶備忘錄）

from functools import lru_cache

@lru_cache(maxsize=None)
def cows_recursive(n: int) -> int:
    if n <= 0: return 0
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 3
    if n == 4: return 4
    return cows_recursive(n - 1) + cows_recursive(n - 3)

迭代 O(1) 空間實現（推薦）

def cows_iterative(n: int) -> int:
    if n <= 0: return 0
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 3
    if n == 4: return 4
    a, b, c, d = 1, 2, 3, 4  # f(n-4), f(n-3), f(n-2), f(n-1)
    for _ in range(5, n + 1):
        a, b, c, d = b, c, d, d + b  # f(n) = f(n-1) + f(n-3)
    return d

複雜度對比

總結

母牛問題本質是線性遞推 f(n)=f(n-1)+f(n-3)。Python 使用 lru_cache 快速實現備忘錄遞歸，或四變量滾動迭代達到 O(1) 空間，均可輕鬆應對大 N（如 10^6）場景。