习题库——C++习题精讲

大整数相乘

这是一道2018年pdd的笔试第二题。

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

我们该如何计算呢？

分析

这道题千万不要以为是非常简单的问题，因为例子输入的数字和有可能是超出long long int界限的数字，所以不是简单的相乘问题，而是考录到字符串的转换与移位进位的题目。

设计思路：
1.设计一个string res存放答案而且空间要提前开好。开len1+len2大小的空间，而且都要置为‘0’.
（大家可以验证，3位数*2位数最多只会是5位数，所以我很有自信的开了len1+len2个空间）
2.设计一个进位符cur，在设计一个移位符，因为不是那么简单的乘法运算，还要考录到移位之后是否有进位，
而且还要再加新的数。
3.如果不想多计算得出来的新数该填写在什么位置，最好把所有字符串都颠倒一下（s1、s2），然后再计算，得到的数可以按照i 和j的递增顺序填写进res。
4.最后要把res再反转一下才是正确的数字顺序，而且要判断第一个字符是否为‘0’，是的话要去掉。

模拟数学中两个数相乘的步骤和思路，如图所示num1=123，num2=45

#include 
#include
#include
using namespace std;string mul(string& s1,string& s2)
{int len1=s1.size();int len2=s2.size();reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());string res(len1+len2,'0');int cur=0;//进位值int offset=0;//移位for(auto x:s1){int num1=x-'0';cur=0;for(int j=0;jint num2=((res[j+offset]-'0')+(s2[j]-'0')*num1+cur);res[j+offset]=(num2%10+'0');cur=num2/10;}if (cur != 0)res[len2+offset] = cur + '0';offset++;}reverse(res.begin(),res.end());if(res[0]=='0'){res.erase(0,1);}return res;
}
int main() 
{string s1;string s2;cin>>s1>>s2; cout<