C语言实现斐波那契数列：从入门到精通

创作时间:

2025-01-21 19:02:48

作者:

@小白创作中心

C语言实现斐波那契数列：从入门到精通

斐波那契数列，又称黄金分割数列，是由意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子引入，因此也被称为“兔子数列”。这是一个在数学和自然界中广泛出现的数列。这个数列的特点是，除了第一个和第二个数外，任何一个数都是前两个数的和。数列通常以1开始（有时候也会从0开始），如下所示：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ······

斐波那契数列的定义如下：
F(n) = F(n-1) + F(n-2)，对于 n>=2，其中 F(n) 表示数列的第 n 项。

斐波那契数列的特性

黄金比例：斐波那契数列中任意两个相邻数的比值趋近于黄金比例（约1.618033988749895）。当 n 趋向于无穷大时，这个比值趋近于黄金比例。
自然界中的出现：斐波那契数列在自然界中频繁出现，例如在植物的叶序和花的排列中，以及在动物的繁殖模式中。
计算机科学中的应用：在计算机科学中，斐波那契数列用于算法设计，如斐波那契堆（Fibonacci heap）是一种高效的数据结构，用于图算法和优先队列。

C语言实现

递归实现

递归方法直观且易于理解，但效率较低。以下是递归实现的代码：

#include <stdio.h>

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

int main() {
    int a = 0;
    scanf("%d", &a);
    int num = fibonacci(a);
    printf("%d", num);
    return 0;
}

递归方法的主要缺点是存在大量重复计算。例如，计算第30个斐波那契数时，某些子问题会被重复计算多次，导致效率低下。

迭代实现

迭代方法通过循环计算，避免了重复计算，效率更高。以下是迭代实现的代码：

#include <stdio.h>

int fibonacci(int n) {
    int a = 1;
    int b = 1;
    int c = 1;
    while (n > 2) {
        a = b;
        b = c;
        c = a + b;
        n--;
    }
    return c;
}

int main() {
    int a = 0;
    scanf("%d", &a);
    int num = fibonacci(a);
    printf("%d", num);
    return 0;
}

迭代方法的时间复杂度为O(n)，空间复杂度为O(1)，是计算斐波那契数列的更优选择。