Problem Description 

 

Fibonacci数列，定义如下：f(1)=f(2)=1,f(n)=f(n-1)+f(n-2) n>=3;

计算第n项Fibonacci数值。

Input

输入第一行为一个整数N，接下来N行为整数m（1<=m<=1000）。

Output

输出为N行，每行为对应的f(m)。

Sample Input

3234

Sample Output

123

 

 

 

 

#include<iostream>

#include<list>

#include<string>

using namespace std;

list<int> BigAddList(list<int> La,list<int> Lb )

{

list<int> Lc;

list<int> ::iterator it1,it2;

it1=La.begin();

it2=Lb.begin();

int carry=0;

while(it1!=La.end()||it2!=Lb.end())

{

int c=carry;

if(it1!=La.end())

{

c=c+(*it1);

it1++;

}

if(it2!=Lb.end())

{

c=c+(*it2);

it2++;

}

carry=c/10;

Lc.push_back(c%10);

}

if(carry>0) Lc.push_back(carry);

Lc.reverse();

return Lc;

}

 

int main()

{

int o;

cin>>o;

for(int v=0;v<o;v++ )

{

list<int>La,Lb,Lc,Ld;

Lc.push_back(1);

La.push_back(1);

Lb.push_back(1);

int T;

cin>>T;

for(int j=3;j<=T;j++)

{

Lc=BigAddList(La,Lb);

La=Lb;

Lb=Lc;

Lb.reverse();

}

for(list<int>::iterator it=Lc.begin();it!=Lc.end();it++)

{

cout<<*it;

}

Lc.clear();

cout<<endl;

}

}