用C++完成菲波数小程序

问题：
斐波那契数列，定义如下

  • f(1)=f(2)=1
  • f(n)=f(n-1)+f(n-2) n>=3
    计算第n项菲波数值

输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=60）
输出为N行，每行为对应的f（Pi）


#include <iostream>
using namespace std;

long long fun(int n)
{
    int i;
    long long a1= 1,a2 = 1,an;
    if(n<3) return 1;
    for(i=3;i<=n;i++)
    {
        an = a1 + a2;
        a1 = a2;
        a2 = an;
    }
    return an;
}


int main()
{
    int n;
    int *p;
    cin >> n;
    p = new int[n];
    for(int i = 0;i<n;i++)
        cin >> p[i];

    for(int i =0;i<n;i++)
        cout << fun(p[i]) << endl;
    delete[] p;
    p = 0;
    return 0;
}


//求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2)，
//又必须先计算F(n-3)和F(n-4)。。。。。。以此类推，
//直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果，
//从而得到F(n)要计算很多重复的值，在时间上造成了很大的浪费，
//算法的时间复杂度随着N的增大呈现指数增长，时间的复杂度为O(2^n)，即2的n次方
#include <iostream>

using namespace std;

int64_t Fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

int main(int argc, char const *argv[])
{
    for (int i = 0; i < 100; i++)
    {
        cout << "Fib(" << i << ")"
             << "=" << Fib(i) << endl;
    }

    return 0;
}

//从n(>2)开始计算，用F(n-1)和F(n-2)两个数相加求出结果，
//这样就避免了大量的重复计算，它的效率比递归算法快得多，
//算法的时间复杂度与n成正比，即算法的时间复杂度为O(n).
#include <iostream>

using namespace std;

int64_t Fib(int n)
{
    if(n == 0)
        return 0;
    if(n <= 2)
        return 1;
    //first 是第n-2个数；second是第n-1个数
    int64_t first = 0;
    int64_t second = 1;
    while(0 < n--)
    {
        second += first; 
        first = second - first; 
    }
    return first + second;
}

int main(int argc, char const *argv[])
{
    for(int i =0; i< 50;i++)
    {
        cout << "Fib(" << i << ")=" << Fib(i) <<endl;
    }
    return 0;
}

#include <iostream>
using namespace std;

long long f(int n)
{
    long long n1 = 1,n2= 1,n3=0;
    for(int i=3;i<=n;i++)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    return n3;
}
int main()
{
      int n,m;
      cin>>n;
      for(int i=0;i<n;i++)
      {
            cin>>m;
            if(m<=2)
                cout<<"1"<<endl;
            else
                cout<<f(m)<<endl;
      }
      return 0;
}



#include "stdio.h"


void main()
{
    int f1=1,f2=1;
    
    int i,n,t;
    scanf("%d",&n);
    for(i=3;i<=n;i++){
        t = f2;
        f2=f1+f2;
        f1=t;
    }
    printf("%d",f2);
}