一、背景介绍

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

【兔子繁殖问题】

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

依次类推可以列出下表：

经过月数	0	1	2	3	4	5	6	7	8	9	10	11	…
幼仔对数	1	0	1	1	2	3	5	8	13	21	34	55	…
成兔对数	0	1	1	2	3	5	8	13	21	34	55	89
总体对数	1	1	2	3	5	8	13	21	34	55	89	144

幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。

简言之，就是以下五点：

（1）中文名：斐波那契数列

（2）别名：黄金分割数列、兔子数列

（3）英文名:Fibonacci sequence

（4）提出者：莱昂纳多·斐波那契

（5）表达式：F[n]=F[n-1]+Fn-2

二、思路分析

三、代码实现

//递归法实现斐波那契数列问题求解
#include<stdio.h>
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}

四、拓展阅读

【说明：目前来讲要求了解即可，用到的时候知道怎么查即可。不过，目前在我看来，应该用不到🈚。。。】

1.特性

1.平方与前后项

【特别说明：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶】

2.奇数项求和

3.偶数项求和

4.平方求和

5.两倍项关系

6.其他公式

2.应用

1.黄金分割

随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值 0.6180339887……

2.杨辉三角

3.矩形面积

斐波那契数列前几项的平方和可以看做不同大小的正方形，由于斐波那契的递推公式，它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积。则可以得到如下的恒等式：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t6iut1ud-1651491444176)(https://bkimg.cdn.bcebos.com/formula/4e3acee4042a4f988211432f74909cf6.svg)]

4.自然界中“巧合”

两位法国科学家通过对花瓣形成过程的计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列长出花瓣。

3.相关问题

①有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第 10 级台阶有几种不同的走法?

这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……

1，2，3，5，8，13…… 所以，登上十级，有 89 种走法。

【说明：由于跳台阶这个问题出现频率较高，所以我单独写了一篇博文去分析这个问题，感兴趣的小伙伴可以移步我的【C/C++专题练习总结】看一下】

②求递推数列的通项公式

由数学归纳法可以得到：

，将斐波那契数列的通项式代入，化简就得结果。

参考：
百度百科介绍

五、迭代实现斐波那契数求解代码演示

//迭代法实现第n个斐波那契数求解
#include<stdio.h>
int fib(int n)
{
	if (n <= 2)
		return 1;
	int a = 1, b = 1,ret=0;
	int i;
	for (i = 3;i <= n;i++)
	{
		ret = a + b;
		a = b;
		b = ret;
	}
	return ret;
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}