您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計疑難解答

斐波那契兔子問題：經典遞歸與動態規劃的Java實現

編輯：程式設計疑難解答

經典算法題：兔子繁殖問題的數學本質與代碼實現

「有一對兔子，從出生後第三個月起每個月都生一對兔子……」這個著名的斐波那契數列起源問題，不僅是遞歸教學的經典案例，更是動態規劃思想的完美入門場景。本文將從數學建模、遞歸實現、迭代優化、矩陣快速冪四個層次徹底攻克此題。

問題數學建模

設F(n)為第n個月兔子總對數：

F(1) = 1（初始一對）
F(2) = 1（第二月仍只有一對，未成熟）
F(n) = F(n-1) + F(n-2)（n≥3：上月所有兔子存活 + 新出生的 = 兩月前已成熟的兔子數）

這正是斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

四種實現方案對比

1. 朴素遞歸（教學用，生產環境禁用）

public long fibRecursive(int n) {
    if (n <= 2) return 1;
    return fibRecursive(n-1) + fibRecursive(n-2);
}
// 時間複雜度：O(2^n)，指數級爆炸，n=50時需數小時

2. 遞歸+備忘錄（自頂向下動態規劃）

Map memo = new HashMap<>();
public long fibMemo(int n) {
    if (n <= 2) return 1;
    if (memo.containsKey(n)) return memo.get(n);
    long res = fibMemo(n-1) + fibMemo(n-2);
    memo.put(n, res);
    return res;
}
// 時間/空間：O(n)，但遞歸深度受棧限制

3. 迭代DP（自底向上，工程首選）

public long fibIterative(int n) {
    if (n <= 2) return 1;
    long prev2 = 1, prev1 = 1, curr = 0;
    for (int i = 3; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}
// 時間O(n)，空間O(1)，無棧溢出風險

4. 矩陣快速冪（大數高性能場景）

public long fibMatrix(int n) {
    if (n <= 2) return 1;
    long[][] base = {{1,1},{1,0}};
    long[][] res = matrixPow(base, n-2);
    return res[0][0] + res[0][1]; // F(n) = M^(n-2)[0][0]*F(2) + M^(n-2)[0][1]*F(1)
}
// 時間O(log n)，適合n極大（如10^9）場景

工程落地完整代碼

public class RabbitProblem {
    public static void main(String[] args) {
        int months = 12;
        System.out.println("月份\t兔子對數");
        for (int i = 1; i <= months; i++) {
            System.out.println(i + "\t" + fibIterative(i));
        }
    }
    
    // 推薦：迭代版本，兼顧性能與可讀性
    private static long fibIterative(int n) {
        if (n <= 2) return 1;
        long a = 1, b = 1, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}