C++大整数相乘(转化为大整数相加问题)
一、问题描述:
有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。例如:
输入:72106547548473106236 982161082972751393
输出:70820244829634538040848656466105986748
二、问题分解
采用99108*213来作为例子讲解,人工计算两个整数相乘的过程如下图:
将s1与s2的每一位单独相乘,得到1、2、3三个字符串,再将三个字符串按照一定的偏移量进行相加,得到最后的结果。
问题就分解为:
(1)求字符串s1与s2中的每一个字符相乘得到的字符串表示结果,将所有结果存进vector中。
(2)将vector中所有的字符串,按照一定的偏移量进行相加,得到最终的字符串表示结果。
注意:在乘法和加法过程中,要注意进位的问题;
三、源代码
主函数:
读入两个字符串表示的大整数,对特殊情况进行处理:
Process函数:处理大整数和大整数相除,主要分为两部分,OneMulty函数调用和addString函数调用;
1、其中OneMulty函数实现s1和s2中的每一个字符相乘的结果,并将所有结果存在vec中。
2、addString函数实现vec中所有字符串按一定偏移量相加的结果。
将代码按照最后一个图到第一个图组合,可以获得完整的源代码。经测试,程序可以保证正确运行。