Question

c++ 的高精度（至少1000位）斐波那契数列问题 求改正代码

我先编了加法器。。没有问题
我的加法器代码是
#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0;

int main()
{
string s1,s2;
int a[1200],b[1200],he;
int i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>s1>>s2;

a[0]=s1.length();
for(i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-'0';
}

b[0]=s2.length();
for(i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-'0';
}

he=(a[0]>b[0]?a[0]:b[0]);

for(i=1;i<=he;i++)
{
a[i]+=b[i];
a[i+1]+=a[i]/10;
a[i]%=10;
}

he++;

while((a[he]==0)&&(he>1))
he--;

for(i=he,s=0;i>=1;i--,s++)
{
sum[s]=a[i]+'0';
}

cout<<sum;

}

以上应该没有问题，不需更正

然后再从这个加法器改成斐波那契数列这题。。
要求是高精度！1000位
斐波那契数列就是1,1,2,3,5,8,13,21。。。f(n)=f(n-1)+f(n-2)
改完就有问题了。。
我输入n等于1——7都没问题
但n=8就出问题了，应该是8+13=21但却输出31
好像只要是一个n-1位数加一个n位数就会在最高位额外多1。。
这是怎么回事。。
改成斐波那契数列后的代码是
#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0,m=0,n;
int main()
{
cin>>n;
string s1,s2;
int a[1200],b[1200];
int he,i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
s1="1";
s2="1";
for(m=2;m<n;m++)
{
a[0]=s1.length();
for(i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-'0';
}
b[0]=s2.length();
for(i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-'0';
}
he=(a[0]>b[0]?a[0]:b[0]);
for(i=1;i<=he;i++)
{
a[i]+=b[i];
a[i+1]+=a[i]/10;
a[i]%=10;
}
he++;
while((a[he]==0)&&(he>1))
he--;
for(i=he,s=0;i>=1;i--,s++)
{
sum[s]=a[i]+'0';
}
s1=s2;
s2=sum;
}
cout<<s2;
}

求改正。

Answer 1

应该把memset()调用放在for循环中，每次计算之前都应该将a和b“清零”，修改如下：

#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0,m=0,n;
int main()
{
cin>>n;
string s1,s2;
int a[1200],b[1200];
int he,i;
//注意这里
s1="1";
s2="1";

for(m=2;m<n;m++)
{
memset(a,0,sizeof(a));//注意这里
memset(b,0,sizeof(b));//注意这里
a[0]=s1.length();
for(i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-'0';
}
b[0]=s2.length();
for(i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-'0';
}
he=(a[0]>b[0]?a[0]:b[0]);
for(i=1;i<=he;i++)
{
a[i]+=b[i];
a[i+1]+=a[i]/10;
a[i]%=10;
}
he++;
while((a[he]==0)&&(he>1))
he--;
for(i=he,s=0;i>=1;i--,s++)
{
sum[s]=a[i]+'0';
}
s1=s2;
s2=sum;
}
cout<<s2<<endl;

}

Answer 2

#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0,m=0,n;
int main()
{
cin>>n;
string s1,s2;
int a[1200],b[1200];
int he,i;
//注意这里
s1="1";
s2="1";

for(m=2;m<n;m++)
{
memset(a,0,sizeof(a));//注意这里
memset(b,0,sizeof(b));//注意这里
a[0]=s1.length();
for(i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-'0';
}
b[0]=s2.length();
for(i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-'0';
}
he=(a[0]>b[0]?a[0]:b[0]);
for(i=1;i<=he;i++)
{
a[i]+=b[i];
a[i+1]+=a[i]/10;
a[i]%=10;
}
he++;
while((a[he]==0)&&(he>1))
he--;
for(i=he,s=0;i>=1;i--,s++)
{
sum[s]=a[i]+'0';
}
s1=s2;
s2=sum;
}
cout<<s2<<endl;

}