【C语言】斐波那契数列

一.斐波那契数列是什么？

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（*n ≥ 2，n ∈ N）

大致就是每一项都等于前两项之和的数列

二. 实现斐波那契数列的两种方式

1. 递归实现

通过斐波那契数列的定义可以发现规律是：F(n) = F(n-1)+F(n-2)，但前两项都是1

代码：

#include <stdio.h>
int fib(int input){
    if (input <= 2) {
        return 1;//前两项都为1，所以直接返回1即可
    }
    return fib(input - 1) + fib(input - 2);
}
void main() {
    int input = 0;
    scanf("%d",&input);
    printf("第%d位斐波那契数为:%d",input,fib(input));
}

运行结果：

图解：

注意：当输入的数较大时就会特别慢，原因是出现了很多的不必要的重复计算，极大的影响了计算效率

2. 循环实现（简单高效）

2.1 for循环实现

代码：

#include <stdio.h>
int fib(int input) {
    int f1 = 1, f2 = 1, f3 = 1;
    for (int i = 2; i < input;i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}
void main() {
    int input = 0;
    scanf("%d",&input);
    printf("第%d位斐波那契数为:%d",input,fib(input));
}

2.2 while循环实现

代码：

#include <stdio.h>
int fib(int input) {
    int f1 = 1, f2 = 1, f3 = 1;
    while (input > 2) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
        input--;
    }
    return f3;
}
void main() {
    int input = 0;
    scanf("%d",&input);
    printf("第%d位斐波那契数为:%d",input,fib(input));
}

斐波那契数列的实现方法有递归和循环，但通过对比能看出来，递归过程中产生很多了多余的计算，使得递归算法的时间复杂度很大，所以我们更常用循环的方法实现。

关于C语言实现斐波那契数列的讲解到这里就结束了，如果有什么不对的地方欢迎在评论区指正，谢谢支持~