题解（全ACGO最正经）

斐波那契数列可以用递归和递推的方法来做。

首先，我们要知道递归是什么，递归就函数自己调用自己，由大到小，有一个终止边界，例如：

int recur(int n){
    if(n==0)
        return 0;
    cout<<n<<" ";
    recur(n-1);
}

这个递归代码实现了倒序输出数据。

递推和递归相反，递推是从小到大，递归是从大到小，递推的本质是循环迭代，并不能像递归函数调用自己，就像平常写的for,while循环，例如：

for(int i=1;i<=10;i++)
    cout<<i<<" ";

int i=1;
while(i<=10){
    cout<<i<<" ";
    i++;
}

这两个都能实现正序输出数字，这就是递推的原理。

说了这么多，接下来上代码

递归解法：

#include <iostream>
using namespace std;
int Fibonacci(int n){
    if(n==1||n==2)
        return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cout<<Fibonacci(a[i])%1000<<endl;
    return 0;
}

递推解法：

#include <iostream>
using namespace std;
int Fibonacci(int n){
    if(n==1||n==2)
        return 1;
    int a=1,b=1,c;
    for(int i=3;i<=n;i++){
        c=a+b;
        a=b;
        b=c;
    }
    return b;
}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cout<<Fibonacci(a[i])%1000<<endl;
    return 0;
}

认真看到最后的给个赞呗！