高精度算法II(乘法)

Ysjt | 深 ™

2024-06-22 11:13:33

发布于：广东

16阅读

0回复

0点赞

欢迎来到高精度算法的第二站:高精度乘法,详情见目录:传送门

高精度乘法原理:

欢迎来到高精度算法的第二站:高精度乘法
在这之前,我们先要认识高精度乘法,高精度乘法归根结底还是要用到数学乘法的基本原理,先把一个大整数分拆成各个数位,过程:

将两个大整数相乘，从低位开始逐位相乘，得到部分乘积；
将每一位的部分乘积相加，考虑进位；
最终得到的结果就是两个大整数的乘积。
举例说明：
假设要计算 12345 * 6789。
首先，逐位相乘得到部分乘积：59=45、49=36、39=27、29=18、1*9=9。
然后，将这些部分乘积相加考虑进位：5 + 3（进位）= 8、6 + 4 + 2（进位） = 12、2 + 7 + 1（进位） = 10、1 + 8 = 9、0（进位）= 0。
最终结果为：83965705。
通过这种方法，可以实现大整数的高精度乘法运算。
那么接下来就请看代码详解:

代码详解:

这次咱们调换一下顺序,先亮出例题和代码,接着再来讲解:
例题:A*Bproblem-洛谷

#include <iostream>
#include <vector>
using namespace std;

// 高精度乘法
vector<int> multiply(vector<int>& num1, vector<int>& num2) {
    int len1 = num1.size();
    int len2 = num2.size();
    vector<int> result(len1 + len2, 0);

    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];

            result[i + j] += sum / 10; // 进位
            result[i + j + 1] = sum % 10; // 当前位
        }
    }

    // 移除结果中的前导零
    int i = 0;
    while (i < result.size() && result[i] == 0) {
        i++;
    }
    if (i == result.size()) return {0};
    return vector<int>(result.begin() + i, result.end());
}

int main() {
string str1, str2;
    cin >> str1;
    cin >> str2;

    // 将字符串转换为vector<int>，每一位作为vector的一个元素
    vector<int> num1(str1.begin(), str1.end());
    vector<int> num2(str2.begin(), str2.end());

    // 调用高精度乘法函数
    vector<int> result = multiply(num1, num2);

    // 输出结果
    for (int digit : result) {
        cout << digit;
    }
    cout << endl;

    return 0;
}

当然,这只是个母题,我们默认定义的vector数组是int类型的,所以在这里并没有处理负数的情况,如果需要支持负数的话,还需另外进行操作.
那么今天我们就讲到这儿了,离别是为了更好的相聚,希望下次的高精度除法能够再次与你同行
-Ysjt | 深

高精度算法II(乘法)

高精度乘法原理:

代码详解:

相关参考/引用:

热门讨论