本文共 1863 字，大约阅读时间需要 6 分钟。
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
也是大数运算：
#include #include #include 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 (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 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 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< =0;i--){ cout.width(DLEN); cout.fill('0'); cout<
转载地址：http://ndvvi.baihongyu.com/