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)。
也是大数运算：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 9999
#define MAXSIZE 100
#define DLEN 4
class BigNum{
private:
int num[500];
int len;
public:
BigNum(){len=1;memset(num,0,sizeof(num));}
BigNum(const int a){
int c,d=a;
len=0;
memset(num,0,sizeof(num));
while(d>MAXN){
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
num[len++]=c;
}
num[len++]=d;
}
BigNum(const char *s){
memset(num,0,sizeof(num));
int l=strlen(s);
len=l/DLEN;
if(l%DLEN)len++;
int index=0;
for(int i=l-1;i>=0;i-=DLEN){
int t=0;
int k=i-DLEN+1;
for(int j=k;j<=i;j++)
t=t*10+s[j]-'0';
num[index++]=t;
}
}
BigNum(const BigNum &T):len(T.len){
memset(num,0,sizeof(num));
for(int i=0;i<len;i++)
num[i]=T.num[i];
}
BigNum &operator =(const BigNum &n){
len=n.len;
for(int i=0;i<len;i++)
num[i]=n.num[i];
return *this;
}
bool operator >(const BigNum &T){
if(len>T.len)return true;
else if(len==T.len){
int ln=len-1;
while(num[ln]==T.num[ln]&&ln>=0)ln--;
if(ln>=0&&num[ln]>T.num[ln])return true;
else return false;
}
else return false;
}
bool operator >(const int &t){
BigNum b(t);
return *this>b;
}
BigNum operator +(const BigNum & T){
BigNum t(*this);
int big=T.len>len?T.len:len;
for(int i=0;i<big;i++)
{
t.num[i]+=T.num[i];
if(t.num[i]>MAXN){
t.num[i+1]++;
t.num[i]-=MAXN+1;
}
}
if(t.num[big]!=0)
t.len=big+1;
else t.len=big;
return t;
}
BigNum operator -(const BigNum &T){
bool flag;
BigNum t1,t2;
if(*this>T){
t1=*this;
t2=T;
flag=0;
}
else{
t1=T;
t2=*this;
flag=1;
}
int big=t1.len;
for(int i=0;i<big;i++){
if(t1.num[i]<t2.num[i]){
int j=i+1;
while(t1.num[j]==0)j++;
t1.num[j--]--;
while(j>i)
t1.num[j--]+=MAXN;
t1.num[i]+=MAXN+1-t2.num[i];
}
else t1.num[i]-=t2.num[i];
}
t1.len=big;
while(t1.num[len-1]==0&&t1.len>1){
t1.len--;
big--;
}
if(flag)
t1.num[big-1]=0-t1.num[big-1];
return t1;
}
void print(){
cout<<num[len-1];
for(int i=len-2;i>=0;i--){
cout.width(DLEN);
cout.fill('0');
cout<<num[i];
}
cout<<endl;
}
};
int main()
{
freopen("C:\\in.txt","r",stdin);
int N;
scanf("%d",&N);
for(int i=1;i<=N;i++){
int num;
scanf("%d",&num);
BigNum t1(1);
//t1.print();
BigNum t2(t1);
//t2.print();
BigNum t3=t1+t2;
//t3.print();
if(num==1){t1.print();continue;}
if(num==2){t2.print();continue;}
for(int i=3;i<=num;i++){
t3=t1+t2;
t1=t2;
t2=t3;
}
t3.print();
}
return 0;
}