大数相乘算法（相加，相减）
所谓大数相乘，就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。
假设有A和B两个大数，位数分别为a和b。根据我们平常手动计算乘法的方式可以看出，最终的结果的位数c一定小于等于a+b。
由于数字无法用一个整形变量存储，很自然的想到用字符串来表示一串数字。然后按照乘法的运算规则，用一个乘数的每一位乘以另一个乘数，然后将所有中间结果按正确位置相加得到最终结果。可以分析得出如果乘数为A和B，A的位数为m，B的位数为n，则乘积结果为m+n-1位（最高位无进位）或m+n位（最高位有进位）。因此可以分配一个m+n的辅存来存储最终结果。为了节约空间，所有的中间结果直接在m+n的辅存上进行累加。
【大数相乘算法（相加，相减）】
#include
#include
using namespace std;
string BigNumMultiply(string str1, string str2)
{
int size1 = str1.size(), size2 = str2.size();
string str(size1 + size2, '0');
for (int i = size2 - 1;
i >= 0;
--i)
{
int mulflag = 0, addflag = 0;
for (int j = size1 - 1;
j >= 0;
--j)//将str2中的每个元素分别乘以str1中的元素
{
int temp1 = (str2[i] - '0')*(str1[j] - '0') + mulflag;
//将前一次的进位加进来即当前两位数相乘结果
mulflag = temp1 / 10;
//两数相乘的进位
temp1 = temp1 % 10;
//当前位数字
int temp2 = str[i + j + 1] - '0' + temp1 + addflag;
//将相乘结果进行相加，相乘结果位对应数字计算
str[i + j + 1] = temp2 % 10 + 48;
//将数字转化为字符，即相乘结果的第i+j+1位
addflag = temp2 / 10;
//相乘结果相加之后的进位
}
str[i] += mulflag + addflag;
//把上次相乘的进位和相加的进位进行相加
}
if (str[0] == '0')
str = str.substr(1, str.size());
//获取从第1位开始的长度为str.size()的字符串
return str;
}int main()
{
while (cin >> str1 >> str2)
{
cout << str1 << "*" << str2 << "=" << endl;
cout << BigNumMultiply(str1, str2) << endl;
}
return 0;
} 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 读书笔记|《白话大数据和机器学习》学习笔记1