大菲波数
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16125 Accepted Submission(s): 5355
Problem Description
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
Input
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
Output
输出为N行，每行为对应的f(Pi)。
Sample Input
5
1
2
3
4
5
1
2
3
4
5
Sample Output
1
1
2
3
5
1
2
3
5
网上查了下第1000个数字有200+位数，因此只能用大数加法模版
代码：
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
void Add(char a[],char b[],char d[])
{
char c[500];
int lena=strlen(a),lenb=strlen(b);
int i,j,len;
len=lena>lenb?lena:lenb;
len++;
c[0]='\0';
for(i=1;i<=len;i++)
c[i]='0';
for(i=1;i<=lena;i++)
c[i]+=a[lena-i]-48;
for(i=1;i<=lenb;i++)
c[i]+=b[lenb-i]-48;
for(i=0;i<=len;i++)
if(c[i]>57)
{
c[i]-=10;
c[i+1]++;
}
for(i=len;i>1;i--)
if(c[i]==48)
len--;
else
break;
for(i=0;i<=len;i++)
d[i]=c[len-i];
}
char list[1001][1000]={"0","1","1"};
int main(void)
{
int t,n;
cin>>t;
while (t--)
{
cin>>n;
for (int i=3; i<=n; i++)
Add(list[i-1],list[i-2],list[i]);
cout<<list[n]<<endl;
}
return 0;
}