数组例题——斐波那契数列

在700多年前，意大利有一位著名数学家斐波那契在他的《算盘全集》一书中提出了这样一道有趣的兔子繁殖问题：兔子在出生两个月以后，就具有生殖后代的能力。假设一对兔子，每月都能生一对兔子，生出来的每一对小兔子，在出生两个月后，也每月生一对兔子。那么，由一对刚出生的小兔子开始，连续不断地繁殖下去，在某个指定的月份有多少对兔子？

通过表格来分析：

通过最后一行的分析，可知，第1、2个月后，兔子的对数都是1，从第3个月开始，兔子的对数是前面两个月的和。如果第$n$个月后兔子的对数用$a_n$来表示，用高中数列的知识来描述，有：

$a_n=\left\{ \begin{aligned} 1(n=1,2) \\ a_{n-1}+a_{n-2}(n>=3) \end{aligned} \right.$

我们可以借助三个变量来依次推导计算：

开始时：$f1=1,f2=1$

在计算过程中重复执行以下步骤：

1. $f3=f2+f1$
2. $f1=f2$
3. $f2=f3$

注意第2步和第3步顺序不能交换！

这样依次推导的算法，称为递推算法。

#include<iostream>
using namespace std;
int main()
{
	int n;
	long long f1,f2,f3;     //值增加较快，使用long long
	cin>>n;
	f1 = f2 = 1;
	
	if(n>=1) cout<<1<<":"<<f1<<endl;
	if(n>=2) cout<<2<<":"<<f2<<endl;
	
	for(int i=3;i<=n;i++){
		f3 = f2+f1;
		cout<<i<<":"<<f3<<endl;
		f1 = f2;
		f2 = f3;
	}
    return 0;
}

当然可以使用数组来解决问题：

#include<iostream>
using namespace std;
long long a[93] = {0,1,1};  //数组元素部分赋值 
int main()
{
	int n;
	cin>>n;
	for(int i=3;i<=n;i++) a[i] = a[i-1]+a[i-2];
	for(int i=1;i<=n;i++) cout<<i<<":"<<a[i]<<endl;
    return 0;
}

其实斐波那契数列有通项公式：

$a_n = \dfrac{1}{\sqrt{5}}\left[\left({\dfrac{1+\sqrt{5}}{2}}\right)^n-\left({\dfrac{1-\sqrt{5}}{2}}\right)^n\ \right]$

又称为“比内公式”，是用无理数表示有理数的一个范例。