C++实现大数乘法

2024-08-30 05:20

文章标签 c++ 实现大数乘法

本文主要是介绍C++实现大数乘法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先来看一下原题目：

在编程的过程中，我们可能会遇到两个很大的数相乘的情况，此时计算的结果很有可能会超过整型的最大值，如果我们继续采取常规的方法对两个数相乘的话可能就会出现问题，此时我们就需要以字符串的形式来读取两个数字，并且编写一个函数计算他们的乘积

首先我们需要判断两个操作数是否含0，因为0乘任何数字都是0，所以只要两个数中出现过0，那么计算出来的结果也为0

        if (s == "0" || t == "0"){return "0";}

接下来我们就需要知道s和t有几个数字：

        int m = s.size();int n = t.size();

我们知道m*n的结果的数字个数不可能大于m+n，所以我们初始化一个大小为m+n的数组pos来存放每一位的乘积结果：

        vector<int> pos(m + n, 0);

接下来我们正式进入大数的运算环节：

我们先从个位数开始运算：

首先我们需要把相乘数位上面的数字转换为整型，然后创建一个新的变量mul用来保存计算结果，再设置两个p1和p2分别用来保存乘积要放在位置的数和进位位置的数，最后再创建一个sum变量用于计算当前位上的总和。

sum除以10的余数就是当前位上应该存的数，sum除以十的整数部分就是进位数：

        for (int i = m - 1; i >= 0; i--){for (int j = n - 1; j >= 0; j--){int mul = (s[i] - '0') * (t[j] - '0');int p1 = i + j;int p2 = i + j + 1;int sum = mul + pos[p2];pos[p2] = sum % 10;pos[p1] += sum / 10;}}

最后我们用string类来保存运算结果并且返回：

        string result;for (int num : pos){           result.push_back(num + '0');}

到这里程序就差不多完成了，我们来测试一下看看有没有问题：

我们可以看到这一组用例出现了问题，我们来寻找一下问题：

可以看到，因为我们一开始创建的数组初始化都为0，因为不一定两个数相乘出来的数可以占全m+n个数位，如果两数相乘没有占满时，最高位就会多出一个0，我们此时就需要把0去除：

        string result;for (int num : pos){if (!(result.empty() && num == 0)){result.push_back(num + '0');}}return result.empty() ? "0" : result;

我们把所有的代码整合一下：

class Solution
{
public:string solve(string s, string t){if (s == "0" || t == "0"){return "0";}int m = s.size();int n = t.size();vector<int> pos(m + n, 0);for (int i = m - 1; i >= 0; i--){for (int j = n - 1; j >= 0; j--){int mul = (s[i] - '0') * (t[j] - '0');int p1 = i + j;int p2 = i + j + 1;int sum = mul + pos[p2];pos[p2] = sum % 10;pos[p1] += sum / 10;}}string result;for (int num : pos){if (!(result.empty() && num == 0)){result.push_back(num + '0');}}return result.empty() ? "0" : result;}
};

修改以后代码成功运行：