yubing_lml @ 2019-08-19 10:41:26
貌似是高精度乘法出问题了,我自己调试了几个数据也没发现其他错误嘞。
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
using namespace std;
struct number
{
int digit[2003];
int length;
void init()
{
for(int i=0; i<2003; i++)
digit[i]=0;
length=0;
}
number operator * (const number &b) const
{
number ret;
ret.init();
int tmp,carry=0;
for(int j=0; j<b.length; j++)
{
carry=0;
for(int i=0; i<length; i++)
{
tmp=(digit[i]*b.digit[j])+carry;
carry=tmp/10000;
tmp=tmp%10000;
ret.digit[i+j]+=tmp;
ret.length=i+j+1;
}
if(carry!=0)
ret.digit[ret.length++]=carry;
}
return ret;
}
void convert(string str)
{
init();
int j=0,c=1,t=0;
for(int i=str.length()-1; i>=0; i--)
{
t+=(str[i]-'0')*c;
c*=10;
j++;
if(j==4||i==0)
{
digit[length++]=t;
j=0;
c=1;
t=0;
}
}
}
void output()
{
cout.setf(ios::fixed);
cout<<digit[length-1];
for(int i=length-2; i>=0; i--)
cout<<setfill('0')<<setw(4)<<digit[i];
}
};
number multi(number a,number b)
{
number ret;
ret.init();
int tmp,carry=0;
for(int j=0; j<b.length; j++)
{
carry=0;
for(int i=0; i<a.length; i++)
{
tmp=(a.digit[i]*b.digit[j])+carry;
carry=tmp/10000;
tmp=tmp%10000;
ret.digit[i+j]=tmp;
ret.length=i+j+1;
}
if(carry!=0)
ret.digit[ret.length++]=carry;
}
return ret;
}
static number a,b,c;
int main()
{
string m,n;
cin>>m>>n;
a.convert(m);
b.convert(n);
c=a*b;
c.output();
return 0;
}
by 142857cs @ 2019-08-19 10:53:01
把digit数组开到大于4000
by yubing_lml @ 2019-08-19 11:58:18
@142857cs 嘿嘿,找到原因啦!不是因为这个哦!我的digit每个元素存储四位所以够多啦! 真正原因如下——————
正确代码:
tmp=(digit[i]*b.digit[j])+carry;
carry=tmp/10000;
tmp=tmp%10000;
ret.digit[i+j]+=tmp;
carry+=ret.digit[i+j]/10000;
ret.digit[i+j]%=10000;
ret.length=i+j+1;
错误代码:
tmp=(digit[i]*b.digit[j])+carry;
carry=tmp/10000;
tmp=tmp%10000;
ret.digit[i+j]+=tmp;
ret.length=i+j+1;
对比发现,关键两行是
carry+=ret.digit[i+j]/10000;
ret.digit[i+j]%=10000;
也就是说我这样写的话,对每个元素要进行两次进位处理才可以保证数据的正确。 比如测试用例2 12345*65432 \ 如果没有那两行,那么ret.digit[1]的值会是5位数,(第五位数没有进位)不符合digit存储的要求。。。 结果就是1707758040 但是正确答案应该是807758040