使用 C 语言实现斐波那契数列的多种方法

斐波那契数列是一种经典的数学序列，在计算机科学和算法领域有广泛应用。它的定义非常简单：第一个数和第二个数分别是 0 和 1，后续的每一个数都是前两个数的和。数学表示为：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2),

本文将通过 C 语言的几个不同实现，带你深入理解这一经典问题。

方法一：递归实现

递归是实现斐波那契数列最直观的方法，但也有其效率上的问题。

代码示例：

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

优点：

• 简洁明了，代码直观，贴合数学公式。

缺点：

• 重复计算严重。例如 fibonacci(5) 会多次计算 fibonacci(3) 和 fibonacci(2)。
• 时间复杂度为 (O(2^n))，对大输入效率极低。

方法二：使用循环

循环避免了递归中的重复计算，显著提高了效率。

代码示例：

#include <stdio.h>

void fibonacci(int n) {
    int a = 0, b = 1, next;

    if (n <= 0) {
        printf("请输入一个正整数。\n");
        return;
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", a);
        next = a + b;
        a = b;
        b = next;
    }
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);

    fibonacci(n);
    return 0;
}

优点：

• 时间复杂度降为 (O(n))。
• 内存占用较少。

缺点：

• 代码逻辑相比递归稍微复杂，抽象性较低。

方法三：动态规划

动态规划是高效解决斐波那契数列的一个重要方法。它通过保存中间计算结果，进一步优化了计算过程。

代码示例：

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

优点：

• 时间复杂度为 (O(n))。
• 易于扩展，比如添加记忆化缓存。

缺点：

• 需要额外的数组存储，空间复杂度为 (O(n))。

方法四：优化的动态规划（常数空间）

动态规划可以进一步优化，通过只保留最近两个计算值，减少空间复杂度到 (O(1))。

代码示例：

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int a = 0, b = 1, temp;

    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

优点：

• 时间复杂度为 (O(n))。
• 空间复杂度为 (O(1))，最为高效。

缺点：

• 仅适用于按序计算，无法灵活获取任意一项的值。

方法五：矩阵快速幂

通过线性代数方法，利用矩阵的快速幂可以在 (O(\log n)) 的时间复杂度内计算出斐波那契数列的任意一项。

代码示例：

#include <stdio.h>

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;
}

void power(int F[2][2], int n) {
    if (n == 0 || n == 1)
        return;

    int M[2][2] = {{1, 1}, {1, 0}};

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0)
        multiply(F, M);
}

int fibonacci(int n) {
    if (n == 0)
        return 0;

    int F[2][2] = {{1, 1}, {1, 0}};
    power(F, n - 1);

    return F[0][0];
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);

    printf("%d\n", fibonacci(n));
    return 0;
}

优点：

• 时间复杂度为 (O(\log n))。
• 适合计算较大数列项。

缺点：

• 代码复杂度较高，不适合初学者。

总结

选择适合自己的实现方式，根据场景优化代码，才能更好地掌握斐波那契数列的精髓！