A30651.【递推】菲波那契数列c++

闲的没事的我又来水题解了
骗你的其实这篇题解不水
我有3种方法:
1.递推法：
众所周知斐波那契数列第一项和第二项都是1，所以我们要定义一个数组，将它的第一项和第二项赋值为1：

long long f[1000000]; //这行是写在main函数上面的
f[1]=1;f[2]=1;//我下标习惯从1开始，从0开始也可以

菲波那契数列的递推公式是f[i]=f[i-1]+f[i-2];
举个例子：
第5项就是f[5]=f[4]+f[3]就是f[5]=3+2。
注意前两项已经赋值为1了，要从第三项开始推。

for(int i=3;i<=55;i++)//55是a的最大值
			f[i]=f[i-1]+f[i-2];

最后简单的输入输出

while(n--){//for也行
			cin>>t;
			cout<<f[t]%1000<<endl;
		}	

完整递推代码：

#include<bits/stdc++.h> 
using namespace std;
long long f[1000000]; 
int main(){
	int n,t;cin>>n;
	f[1]=1;f[2]=1;
		for(int i=3;i<=1000000;i++)
			f[i]=f[i-1]+f[i-2];
		while(n--){
			cin>>t;
			cout<<f[t]%1000<<endl;
		}	
	
	return 0;
} 

2.直接模拟：
用 a,b,c 表示这三个变量，得到 a=b+c 。每次 i 会加一，相当于把 c 扔掉，把 b 后移得到 c ，把 a 后移得到 b ，然后进而计算新的 a 。

c=a+b;
a=b;
b=c;

这种方法时间复杂度会比较高，而且太麻烦，but很好理解。所以自己写代码
3.公式法：

ACGO不能插入公式，所以放的图片。