StarHui


私信TA

用户名:uq_15565483691

访问量:2320

签 名:

只要你想,世界就会出现奇迹!

等  级
排  名 337
经  验 5195
参赛次数 2
文章发表 24
年  龄 18
在职情况 学生
学  校 西安汽车职业大学
专  业 人工智能

  自我简介:

大一新生一枚 一起学习交流,请加V:StarHui0415 个人公众号:阿辉的大本营 公众号会每天更新一道算法题!!!

解题思路:
                面对高精度的数相乘,我们首先想到的是用数组或者字符串,这里我使用的是 vector容器,因为它有个size函数,比较方便。把数存储到容器中是倒序存储的,当结果大于原来输入的数时,可以直接在后面添加,而不是正序一位一位往后退。算法部分是模拟小学学的乘法,用双层for循环把每个数相乘存储到另一个容器里面,然后进行判断,如果数据还没有处理完,就把每一个没处理完的数据 % 10,然后添加到末尾;如果位数在原来的位数里面,就把原来位数上的数字改为 % 10后的。

            步骤:

                1、先把传入的字符串倒序存入到各自的容器A B里

                2、再把每一个数相乘存储到另一个容器C里

                3、对容器C的数据统一处理,如果在循环i在容器C的大小里,就把此时容器对应i的数字改为 % 10(不用在末尾添加),如果循环的i大于等于C的大小,说明数据还没有处理完,需要在容器C末尾添加 % 10的数

                题解不易,希望大家支持一下,点个评分;也希望大佬们指导改正!!!

注意事项:
                1、数据是倒着存进容器里面的,注意边界问题

                2、对数据进行统一时,要考虑数据没有处理完的情况,这时进应该在末尾加上 %10后的结果;反之就需要在原先的位数 %10即可

                3、注意要消除前导零(“”001“”)这种情况
参考代码:

#include #include using namespace std;

vector mul(vector &A,vector &B)
{
    vector C(A.size() + B.size());//定义容器大小
    for(int i = 0;i < A.size();i++)//使用双层for循环,使每一个数与每一个数相乘
    {
        for(int j = 0;j < B.size();j++)
        {
            C[i + j] += A[i] * B[j];//存入到容器C
        }
    }
    for(int i = 0,t = 0;i < C.size() || t;i++)//对这些数据进行处理,t表示进位。循环要么是i没有循环完,要么是t != 0
    {
        t += C[i];
        if(i >= C.size())//如果数据还没有处理完,就说明结果大于原先的位数,需要添加位数
            C.push_back(t % 10);
        else//反之只需要在原先的位数上处理即可
            C[i] = t % 10;
        t /= 10;//表示进位
    }
    while(C.size() > 1 && C.back() == 0)//消除前导零
    {
        C.pop_back();
    }
    return C;
}

int main()
{
    string a,b;
    cin >> a >> b;
    vector A,B;
    for(int i = a.size() - 1;i >= 0;i--)//倒序存进容器里面
    {
        A.push_back(a[i] - '0');
    }
    for(int i = b.size() - 1;i >= 0;i--)
    {
        B.push_back(b[i] - '0');
    }
    auto C = mul(A,B);//等价于 vector C = mul(A,B)
    for(int i = C.size() - 1;i >= 0;i--)
    {
        cout << C[i];
    }
    cout << endl;
    return 0; 
}

附yxc大佬的模板

vector mul(vector &A, vector &B)
{
    vector C(A.size() + B.size());

    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];

    for (int i = 0, t = 0; i < C.size() || t; i ++ )
    {
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}


 

0.0分

4 人评分

  评论区