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

 

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

---

关于二分查找的讲解到这里就结束了，如果有什么不对的地方欢迎在评论区指正，谢谢支持~

​​​​​​​