求助dalao!!

P1303 A*B Problem

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


|