0
已解决
新手启示者
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数n，要求菲波那契数列中第n个数是多少。n不超过1000
输入描述 Input Description
一行：一个正整数n，n不超过1000
输出描述 Output Description
个正整数，表示菲波那契数列中第n个数是多少
样例输入 Sample Input
5
样例输出 Sample Output
5
0
已采纳
中级启示者
要用高精度
（一看就知道你没学过递推，不然不可能不知道fib92就爆long long了）
0
中级天翼
string add(string s1,string s2){
int a[100010],b[100010],c[100010];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=s1.size();
b[0]=s2.size();
for(int i=1;i<=a[0];i++){
a[i]=s1[a[0]-i]-'0';
}
for(int i=1;i<=b[0];i++){
b[i]=s2[b[0]-i]-'0';
}
int l=max(a[0],b[0]);
for(int i=1;i<=l;i++){
c[i]=a[i]+b[i]+c[i];
c[i+1]=c[i]/10;
c[i]%=10;
}
if(c[l+1]!=0) l++;
string asd="";
for(int i=1;i<=l;i++){
asd+=(char)(c[l-i+1]+48);
}
return asd;
}@汪宇航
0
中级启示者
f[1]="1",f[2]="1";
for(int i=3;i<=n;i++){
f[i]=Plus(f[i-1],f[i-2]);
}
cout<<f[n];注意f数组为string类型，Plus是高精度加法的函数
0
中级天翼
高精度
PS：你都学DP了，怎么递推还看不出来会爆呢？
0
中级天翼
高精【doge】
0
中级天翼
Plus函数：
pos=0;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int i=1;i<=x.size();i++) b[i]=x[x.size()-i]-'0';
for(int i=1;i<=y.size();i++) c[i]=y[y.size()-i]-'0';
for(int i=1;i<=max(x.size(),y.size());i++){
d[++pos]=b[i]+c[i]+jw;
jw=d[pos]/10;
d[pos]%=10;
}
if(jw>=1){
pos++;
d[pos]=jw;
}
jw=0;
string tmp="";
for(int i=pos;i>=1;i--)
tmp+=(char)(d[i]+'0');
return tmp;
main函数：
f[1]="1",f[2]="1";
cin>>n;
for(int i=3;i<=n;i++){
f[i]=Plus(f[i-1],f[i-2]);
}
cout<<f[n];
除了f数组，剩下的都是int
PS：f是string型的
数组都开1010
0
资深天翼
高精度高精度
