萌新求助 高精度的模拟上面是哪里出了问题

P1303 A*B Problem

像素旋转 @ 2021-01-19 11:08:36

#include<iostream>
#include<cstring>
#define min(a,b) (a<b?a:b)
void times(int a[],int b[],int c[],int,int);
int main(void)
{
    using namespace std;
    char str1[2002]{0};
    cin >> str1;
    int num1 = strlen(str1);
    int a[2001]{0};
    for (int i=0; i < num1; i++)
        a[i] = str1[num1 - i - 1] - '0';
    char str2[2002]{0};
    cin >> str2;
    int num2 = strlen(str2);
    int b[2001]{0};
    for (int i = 0; i < num2; i++)
        b[i] = str2[num2 - i - 1] - '0';
    //得到了两个便于进位的反向数组
    int c[4001]{0};
    times(a,b,c,num1,num2);
    int len = 4000;
    while (c[len] == 0)len--;
    len++;
    for (int i=0; i < len; i++)
        cout << c[len-i-1];
    return 0;
}
void times(int a[],int b[],int c[],int num1,int num2)
{
    int *p=a,*q=b,*k=c,i=0;
    //想办法让*顺序为位数多的在上位数低的做循环
    //下面第一个循环控制整体循环min次,k持续进一位保证模拟乘法
    for (; k < c + min(num1, num2); k++) {
        int d[2001]{0};
        int* l = k,i2=0/*i2用于记录d中存放的长度*/;
        if (min(num1, num2) == num1) {
            //for(;p<a+num1;p++)
            for (p=a,q=b; q < b + num2; q++) {
                d[i] += (*p) * (*q);
                if (d[i] > 9) {
                    d[i + 1] += 1;
                    d[i] -= 10;
                }
                i++;
            }
            d[i]>0?(i2 = i):(i2= i - 1);
            i = 0;
            p++;
        }
        else {
            //for(;q<b+num2;q++)
            for (p=a,q=b; p < a + num1; p++) {
                d[i] += (*p) * (*q);
                if (d[i] > 9) {
                    d[i + 1] += 1;
                    d[i] -= 10;
                }
                i++;
            }
            d[i] > 0 ? (i2 = i) : (i2 = i - 1);
            i = 0;
            q++;
        }
        //i2保存了d[]的位数
        //以上语句使得d[]中每次存的都是我们需要的将加换乘的数
        for (int i=0; l < k + i2; l++,i++) {
            *l+=d[i];
            if (*l > 9) {
                *(l + 1) += 1;
                *l -= 10;
            }
     }
    }
    return;
}

我希望的是模拟多位数之间的竖式乘法过程


by _caiji_ @ 2021-01-19 23:13:16

高精乘不用这么麻烦,而且越麻烦越容易错,整个乘法过程核心代码长这样:

for(int i=0;i<l1;i++){
        for(int j=0;j<l2;j++){
            ans[i+j]+=a[i]*b[j];//建议背这句话,这是高精乘核心
            ans[i+j+1]+=ans[i+j]/10;//进位,把这一位的结果的十位数放在下一位
            ans[i+j]=ans[i+j]%10;//去掉十位
        }
    }

by _caiji_ @ 2021-01-19 23:15:09

@像素旋转 建议背高精模版,具体可以参考题解,自己写太容易出错了


by 像素旋转 @ 2021-01-20 09:34:54

@caijianhong 感谢大佬,自己写是真的debug时一点头绪都没有


|