C 語言驗證費波那契數列 F_n+1/F_n 趨近黃金分割率 1.618

數學背景

費波那契數列定義：F₁=1, F₂=1, Fₙ=Fₙ₋₁+Fₙ₋₂ (n≥3)。相鄰項比值 Fₙ₊₁/Fₙ 隨 n 增大趨近黃金分割率 φ = (1+√5)/2 ≈ 1.6180339887。本文提供 C 語言程序計算並輸出該比值序列。

完整程序代碼

#include <stdio.h>

// 遞歸計算第 n 項 (教學演示用，實際建議迭代)
long long fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    printf("n\tF(n)\tF(n+1)\tRatio F(n+1)/F(n)\n");
    for (int i = 1; i < 20; i++) {
        long long fn = fib(i);
        long long fn1 = fib(i + 1);
        double ratio = (double)fn1 / fn;
        printf("%d\t%lld\t%lld\t%.10f\n", i, fn, fn1, ratio);
    }
    return 0;
}

運行結果

n	F(n)	F(n+1)	Ratio F(n+1)/F(n)
1	1	1	1.0000000000
2	1	2	2.0000000000
3	2	3	1.5000000000
4	3	5	1.6666666667
5	5	8	1.6000000000
6	8	13	1.6250000000
7	13	21	1.6153846154
8	21	34	1.6190476190
9	34	55	1.6176470588
10	55	89	1.6181818182
11	89	144	1.6179775281
12	144	233	1.6180555556
13	233	377	1.6180257511
14	377	610	1.6180371353
15	610	987	1.6180327869
16	987	1597	1.6180344478
17	1597	2584	1.6180338134
18	2584	4181	1.6180340557
19	4181	6765	1.6180339632

比值雙向震盪收斂至 1.6180339887…，驗證 lim(n→∞) Fₙ₊₁/Fₙ = φ。

代碼優化版 (迭代 O(n)、防溢出)

#include <stdio.h>

int main() {
    unsigned long long a = 1, b = 1; // F(1), F(2)
    printf("n\tF(n)\tF(n+1)\tRatio\n");
    for (int n = 1; n < 93; n++) { // 93 項後溢出 64 位無符號
        unsigned long long c = a + b;
        double ratio = (double)c / b;
        printf("%d\t%llu\t%llu\t%.10f\n", n, b, c, ratio);
        a = b;
        b = c;
    }
    return 0;
}

• 迭代避免遞歸指數級重複計算。
• `unsigned long long` 支持到第 93 項 (12200160415121876738)。
• 若需更大項數，引入 GMP 庫或手動實現大整數加法。

數學證明要點

由特征方程 x² = x + 1 得根 φ = (1+√5)/2, ψ = (1-√5)/2。
通項公式 (Binet) Fₙ = (φⁿ - ψⁿ)/√5。
因 |ψ| < 1，當 n→∞ 時 ψⁿ → 0，故 Fₙ₊₁/Fₙ → φ。