大数相乘（c语言/c++）

方法一：做加法

思路：模拟竖乘过程。将num2从后往前一个一个的去乘num1.然后累加。在累加的时候记得在末尾补0.补的0的个数就是第二个字符串中当前i与长度-1的距离。

代码：

string multiply(string num1, string num2) {if(num1=="0"||num2=="0") //其中有一个为0就直接返回0了return "0";string ans = "0";int n = num1.size(), m = num2.size();for(int i=m-1;i>=0;--i) //遍历字符串2中的每一位{string cur; //用来记录当前字符乘num1所得的字符串int add = 0; //进位for (int j = m - 1; j > i; j--) {cur.push_back(0); // 末尾补上0}int y = num2.at(i) - '0'; //转化为整数for(int j=n-1;j>=0;--j){int x = num1.at(j) - '0';int product = x * y + add; //相乘结果cur.push_back(product%10); //取余add = product/10; //进位}if(add!=0) //不等于0表明在相乘后位数加1了{cur.push_back(add%10);add /=10;}reverse(cur.begin(),cur.end());//转过来，因为之前是个位数在前for(auto &ch:cur) //转化为字符串，&表示引用ch += '0';ans = addStrings(ans,cur); //累加}return ans; }// 大数相加string addStrings(string &num1, string &num2) {int i = num1.size() - 1, j = num2.size() - 1, add = 0;string ans;while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.at(i) - '0' : 0;int y = j >= 0 ? num2.at(j) - '0' : 0;int result = x + y + add;ans.push_back(result % 10);add = result / 10;i--;j--;}reverse(ans.begin(), ans.end());for (auto &c: ans) {c += '0';}return ans;}

大数相加可以加这边博文解释：

大数相加

方法二、做乘法

明确两点：

令 m 和 n 分别表示num1和num2的长度，并且它们均不为 0，则 num 1

和 num2的乘积的长度为m+n−1 m+n。对于任意 0≤i<m 和 0≤j<n，num [i]×num 2[j] 的结果位于ansArr[i+j+1]。

代码：

string multiply(string num1, string num2) {int n = num1.size(),m = num2.size();if(num1=="0"||num2=="0")return "0";vector<int>ans(m+n,0);for(int i=m-1;i>=0;--i){int y = num2[i] - '0';for(int j=n-1;j>=0;--j){int x = num1[j] - '0';ans[i+j+1] +=x*y; //将相乘结果放到数组中}}//进位，按上面的，位数高的是在数组前边，所以从后边开始进位for(int i=n+m-1;i>0;i--){// 这里也可以不用判断，因为如果不大于10的话/10 得到的是0if(ans[i]>=10) //大于10的话，往前进位{ans[i-1] +=ans[i]/10;ans[i] %=10;}}//看第一位是否大于0，判断字符起始的位置int index = ans[0] >0?0:1;string res;for(int i=index;i<n+m;++i)res.push_back(ans[i]+'0');return res;}