【笔试题】拼多多2018校招内推编程

2、大数据相乘

问题描述

有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。

输入描述: 空格分隔的两个字符串，代表输入的两个大整数

输出描述: 输入的乘积，用字符串表

问题分析

感觉有点坑，在编译器上可以通过，牛客上通不过，还有这道题没有考虑很多问题，比如说符号问题，输入非法情况，

所以，以后编程题，先做出来，再考虑其他问题。

大数据相乘，就是字符串相乘，有两种普通的方法，移位进位法和逐位相乘法。

代码实现

(1)移位进位法

移位进位法，大体上就是普通人正常计算乘法的思维。

//移位进位法 string Mul(string left, string right) { size_t Lsize = left.size(); size_t Rsize = right.size(); size_t Size = Lsize + Rsize; string res(Size, '0'); int takevoer = 0;//进位 int offset = 0;//移位 size_t idx = 1, j = 1; for ( idx = 1; idx <= Rsize; ++idx) { takevoer = 0; int rightnum = right[Rsize - idx] - '0'; //计算每一位与left相乘 for ( j = 1; j <= Lsize; ++j) { char resBit = res[Size - j - offset] - '0'; int num = rightnum * (left[Lsize - j] - '0') + takevoer + resBit; takevoer = num / 10; res[Size - j - offset] = num % 10 + '0'; } if (takevoer != 0) res[Size - j - offset] = takevoer + '0'; offset++; } //如果没有进位的话，res最高位没有数字 if (res[0] == '0') res.erase(0,1); return res; }

2、逐位相乘法

这个方法是，把计算的结果不考虑进位都保存到一个数组中， 然后在考虑进位。

//逐位相乘法 //将计算的整体结果保存res中，然后再考虑进位 string Mul2(string left,string right) { size_t lSize = left.size(); size_t Rsize = right.size(); size_t Size = lSize + Rsize; vector<int> res(Size, 0); /*int *res = new int[Size]; memset(res, 0, sizeof(int)* Size);*/ for (size_t i = 0; i < Rsize; ++i) { int rightnum = right[Rsize - i - 1] - '0'; for (size_t j = 0; j < lSize; ++j) { int num = rightnum * (left[lSize - j - 1] - '0'); //逆序存放 res[Size - 1 -(i + j)] += num; } } //处理进位 int takeover = 0; size_t idx = 0; for (; idx < Size; ++idx) { int temp = res[Size - idx - 1] + takeover; res[Size - idx - 1] = temp % 10; takeover = temp / 10; } //进位没有处理完 while (takeover != 0) { res[Size - idx - 1] = takeover % 10 ; takeover /= 10; } //处理返回结果 string result; for (size_t index = 0; index < Size; ++index) { result += res[index] + '0'; } //如果没有进位的话，res最高位没有数字 if (result[0] == 0) result.erase(0, 1); return result; } int main() { string data; getline(cin, data); size_t pos = data.find(' '); string left = data.substr(0, pos); string right = data.substr(pos + 1); string res = Mul2(left, right); cout << res << endl; system("pause"); return 0; }