A30490.菲波那契数c++题解

闲的没事的我又来水题解了
骗你的其实这篇题解不水
这道题和A30651.【递推】菲波那契数列很像，只是求出第a向后在%1000。
我有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<=1000000;i++)//1000000是a的最大值
			f[i]=f[i-1]+f[i-2];

最后简单的输入输出，别忘了%1000哦

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.递归法：
递归就是函数自己调用自己废话
先看代码：

long long f(long long x){
    if(x==1||x==2)//写错了就TLE了
        return 1;
    return f(x-1)+f(x-2);
}

其实我递归也不熟
递归完整代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
long long c[65],d[65];
long long f(long long x){
    if(x==1||x==2)
        return 1;
    return f(x-1)+f(x-2);
}
int main(){
   cin>>n;
    for(int i=0;i<n;i++){
        cin>>c[i];
        d[i]=f(c[i]);
    }
    for(int i=0;i<n;i++)
        cout<<d[i]%1000<<endl;
    return 0;
}

3.公式法：

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

我都写了这么多了给个赞吧！