C语言斐波那契数列如何高效求解？

我会从最基础的解法开始,逐步深入到更优的算法，并分析各自的优缺点。

经典递归解法（最直观，但效率极低）

这是最符合数学定义的写法,fib(n) = fib(n-1) + fib(n-2)。

代码:

#include <stdio.h>
// 经典递归
long long fib_recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}
int main() {
    int n = 40; // 尝试计算第40项
    printf("fib(%d) = %lld\n", n, fib_recursive(n));
    return 0;
}

分析:

• 优点: 代码非常简洁，易于理解，直接对应数学公式。
• 致命缺点: 效率极低，存在大量的重复计算，计算 fib(5) 时，fib(3) 会被计算两次，fib(2) 会被计算三次，时间复杂度是指数级的 O(2^n)，当 n 稍大（n > 40），计算时间会变得非常长。

迭代解法（高效且常用）

为了避免递归带来的重复计算,我们可以使用循环（迭代）的方式，从底向上计算。

思路:

1. 初始化 a = 0 (F(0)), b = 1 (F(1))。
2. 循环 n-1 次，在每次循环中：
   • 用 c 存储 a + b 的值。
   • 更新 a 的值为 b。
   • 更新 b 的值为 c。
3. 循环结束后,b 的值就是 F(n)。

代码:

#include <stdio.h>
// 迭代解法
long long fib_iterative(int n) {
    if (n <= 1) {
        return n;
    }
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
int main() {
    int n = 90; // 可以轻松计算到第90项
    printf("fib(%d) = %lld\n", n, fib_iterative(n));
    return 0;
}

分析:

• 优点: 效率极高，时间复杂度是线性的 O(n)，没有重复计算，空间复杂度是 O(1)，只用了几个变量。
• 缺点: 代码比递归解法稍微复杂一点点，但仍然是很容易理解的。

记忆化递归（递归 + 动态规划）

这是一种“两全其美”的方法，它保留了递归的结构，但通过存储已经计算过的结果来避免重复计算。

思路:

1. 创建一个数组（或哈希表）memo 来存储计算过的 Fibonacci 数。
2. 在递归函数中,首先检查 memo[n] 是否已经存在值。
   • 如果存在,直接返回，不再计算。
   • 如果不存在,则进行计算，并将结果存入 memo[n]。

代码:

#include <stdio.h>
#include <stdlib.h>
// 记忆化递归解法
long long fib_memoization(int n, long long* memo) {
    if (n <= 1) {
        return n;
    }
    // 如果已经计算过，直接返回缓存的结果
    if (memo[n] != 0) {
        return memo[n];
    }
    // 否则，计算并存储结果
    memo[n] = fib_memoization(n - 1, memo) + fib_memoization(n - 2, memo);
    return memo[n];
}
int main() {
    int n = 90;
    // 为0到n都分配一个初始值为0的缓存空间
    long long* memo = (long long*)calloc(n + 1, sizeof(long long));
    printf("fib(%d) = %lld\n", n, fib_memoization(n, memo));
    free(memo); // 记得释放内存
    return 0;
}

分析:

• 优点: 时间复杂度优化到了 O(n)，和迭代法一样快，对于某些喜欢递归思维的人来说，可能比迭代法更自然。
• 缺点: 需要额外的 O(n) 空间来存储缓存，并且有递归深度限制（虽然对于 Fibonacci n 不会大到触发栈溢出）。

矩阵快速幂解法（高级解法）

这是一种非常高效的算法,时间复杂度为 O(log n)，适用于需要计算极大 Fibonacci 数的场景。

核心思想: Fibonacci 数列的递推关系可以用矩阵乘法来表示：

| F(n)   |   =  | 1  1 |   | F(n-1) |
| F(n-1) |     | 1  0 |   | F(n-2) |

通过不断自乘这个矩阵,我们可以得到：

| F(n)   |   = | 1  1 |^(n-1)   | F(1) |
| F(n-1) |     | 1  0 |         | F(0) |

问题就转化为计算矩阵 M = [[1, 1], [1, 0]] 的 (n-1) 次幂，而计算一个数的幂，我们可以用 快速幂（二分幂） 算法在 O(log n) 时间内完成。

代码:

#include <stdio.h>
// 定义一个2x2的矩阵结构体
typedef struct {
    long long m[2][2];
} Matrix;
// 矩阵乘法
Matrix matrix_multiply(Matrix a, Matrix b) {
    Matrix result = {{{0, 0}, {0, 0}}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result.m[i][j] += a.m[i][k] * b.m[k][j];
            }
        }
    }
    return result;
}
// 矩阵快速幂
Matrix matrix_pow(Matrix a, int power) {
    Matrix result = {{{1, 0}, {0, 1}}}; // 单位矩阵
    while (power > 0) {
        if (power % 2 == 1) {
            result = matrix_multiply(result, a);
        }
        a = matrix_multiply(a, a);
        power /= 2;
    }
    return result;
}
// 矩阵快速幂解法
long long fib_matrix(int n) {
    if (n <= 1) {
        return n;
    }
    Matrix base = {{{1, 1}, {1, 0}}};
    Matrix result = matrix_pow(base, n - 1);
    return result.m[0][0];
}
int main() {
    int n = 90;
    printf("fib(%d) = %lld\n", n, fib_matrix(n));
    // 尝试一个更大的数
    n = 93;
    printf("fib(%d) = %lld\n", n, fib_matrix(n));
    return 0;
}

分析:

• 优点: 时间复杂度 O(log n)，是所有方法中最快的，尤其适合计算 n 极大的情况。
• 缺点: 代码最复杂，需要理解线性代数中的矩阵乘法和快速幂算法。

通项公式（Binet's Formula）

这是一个纯数学方法,利用黄金分割率来直接计算第 n 项 Fibonacci 数。

公式: F(n) = (phi^n - psi^n) / sqrt(5) phi = (1 + sqrt(5)) / 2 (黄金分割率), psi = (1 - sqrt(5)) / 2。

由于 |psi| < 1，当 n 较大时，psi^n 会趋近于 0，所以公式可以近似为： F(n) = round(phi^n / sqrt(5))

代码:

#include <stdio.h>
#include <math.h>
// 通项公式解法
long long fib_formula(int n) {
    double sqrt5 = sqrt(5.0);
    double phi = (1.0 + sqrt5) / 2.0;
    //