斐波那契数列C语言四种算法

斐波那契数列是一个经典的数学问题，常用于递归、动态规划、矩阵乘法和迭代等不同的计算方法在C语言中实现。以下是四种常见的斐波那契数列算法：

1. **递归**：

   int fibonacci_recursive(int n) {
       if (n <= 1)
           return n;
       else
           return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
   }

这种方法简单直观，但由于递归调用自身导致效率较低，对于较大的`n`值可能会有性能问题。

2. **动态规划**（也叫记忆化搜索）：

   int fibonacci_dp(int n, int* memo) {
       if (memo[n] != -1) return memo[n];
       if (n <= 1) memo[n] = n;
       else memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo);
       return memo[n];
   }

使用数组存储已经计算过的数值避免重复计算，提高了效率。

3. **矩阵快速幂**（利用性质Fibonacci数列的矩阵形式）：
需要使用到矩阵运算库，不是简单的C语言代码，但能大幅加速计算，适用于大数情况：

   // ...省略矩阵操作部分...
   void multiply(int F[2][2], int M[2][2]) {
      int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
      int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
      int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
      int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

      F[0][0] = x;   F[0][1] = y;
      F[1][0] = z;   F[1][1] = w;
   }

4. **迭代**：

   int fibonacci_iterative(int n) {
       int a = 0, b = 1, c;
       if (n == 0) return a;
       for (int i = 2; i <= n; ++i) {
           c = a + b;
           a = b;
           b = c;
       }
       return b;
   }

这种方法通过循环逐步计算，不需要额外的数据结构，适合所有大小的`n`值。