# 求斐波拉契数列的任一项(如：第110项)

xiaoxiao2021-02-28  8

#include<iostream> using namespace std; void Fibonacci(int n) {     if (n == 1 || n == 2)     {         cout << 1 << endl;     }     else     {         int *f1 = new int[1];         f1[0] = 1;         int lenf1=1;         int *f2 = new int[1];         f2[0] = 1;         int lenf2=1;         int *temp;         int count;     for (int i = 3; i <= n; i++)     {         int cn = 0;         int vw = 0;         count=lenf2+1;         temp=new int[count];         temp[0]=0;         int count1=count;         int num1=lenf1;         int num2=lenf2;         vw = f1[num1 - 1] + f2[num2 - 1] + cn;         cn = vw / 10;         temp[count1 - 1] = vw % 10;         count1--;         num1--;         num2--;     while (num2>=0)     {         if(num2==0&&num1==0&&cn!=0)         {             vw=cn;             temp[count1 - 1] = vw % 10;             count1--;             num2--;         }         else if(num2>0&&num1==0&&cn==0)         {             temp[count1 - 1] = f2[num2-1];             count1--;             num2--;         }       else if(num2>0&&num1==0&&cn!=0)        {         vw = f2[num2 - 1]+ cn;         cn = vw / 10;         temp[count1 - 1] = vw % 10;         count1--;         num2--;         }      else if(num2==0&&num1==0&&cn==0)      {         break;      }         else         {         vw = f1[num1 - 1] + f2[num2 - 1] + cn;         cn = vw / 10;         temp[count1 - 1] = vw % 10;         count1--;         num1--;         num2--;         }     }     f1 = new int[lenf2];     for (int j = 0; j < lenf2; j++)     {         f1[j] = f2[j];     }     if(temp[0]==0)     {         f2 = new int[count-1];         for (int k = 0; k <count-1; k++)         {             f2[k]=temp[k+1];         } }     else     {         f2 = new int[count];         for (int k = 0; k <count ; k++)         {             f2[k] = temp[k];         }     }       lenf1=lenf2;       if(temp[0]==0)       {         lenf2=count-1;       }       else       {         lenf2=count;       }     }     if(temp[0]==0)     {         for(int j=1;j<count;j++)         {             cout<<temp[j];         }     }     else     {         for(int j=0;j<count;j++)         {             cout<<temp[j];         }     }     cout << endl;     delete []f1;     delete[]f2;     delete[]temp;     } } int main() {     int n;     while(cin >> n)     {         Fibonacci(n);     }     return 0; }