引入
在上一篇文章中（高精度加法），简单讲解了高精度算法的加法操作
这篇文章将会讲解高精度乘法
原理
高精度乘法的原理与加法有异曲同工之妙，我们直接举一个栗子
99 × 12
对于两个因数，我们分别看作 a 和 b ，积看作 c
因数和积的每个数位从右到左从1开始标号
如图：
那么每一位相乘都可以对应表示为：
根据图示我们可以找到这样的规律：a的下标 + b的下标 - 1 = c的下标
对应相乘之后再对积按数位依次进位即可得到结果
代码实现
创建变量
- 创建两个字符串变量用于输入因数
- 创建三个数组a，b，c 用于模拟竖式计算
- 创建循环变量，以及三个用于保存数组长度的变量
注： 三个整型数组的大小一定要开足
1
2
3
| string s1, s2;
int a[100], b[100], c[100] = { 0 };
int i,j,la,lb,lc;
|
输入因数
- （本例中）使用getline函数输入两个因数
- la，lb分别保存两个因数的长度
- 用两个循环逆序储存两个因数
- （此例中）数组的下标是从后往前移动，字符串的下标是从前往后移动
- 字符串储存的是字符，所以在储存到数组时要减字符0才能得到对应的数字
- 在上述图例中可以看到a，b，c的下标计算都从1开始，为了方便书写代码，在逆序储存因数时要空出下标为0的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
| getline(cin, s1);
getline(cin, s2);
la = s1.size();
lb = s2.size();
for (i = 0; i < la; i++)
{
a[la - i] = s1[i] - '0';
}
for (i = 0; i < lb; i++)
{
b[lb - i] = s2[i] - '0';
}
|
模拟竖式计算
- 用 la+lb 可以得到积的最大位数 lc
- 用两层循环模拟上述栗子中按数位相乘的过程
注：模拟进位时，进位和保留个位两个步骤顺序不能写反
1
2
3
4
5
6
7
8
9
10
11
| lc = la + lb;
for (i = 1; i <= la; i++)
{
for (j = 1; j <= lb; j++)
{
c[i + j - 1] += a[i] * b[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
|
调整循环遍历lc
与加法相同，积的位数不一定是两因数位数之和，所以需要通过从后往前遍历去寻找积的最高位
因为 c 已经初始化了，所以未更改过的位置一定是0，在遍历的过程中只需要判断是否为0即可
因为因数有可能为 0 ，所以循环条件在元素为 0 的同时也****要考虑积为 0 的情况*，*用lc > 0加以限制****
1
2
3
4
| while (c[lc] == 0 && lc > 0)
{
lc--;
}
|
输出得数
因为模拟过程中是逆序操作的，所以在输出时需要逆序输出
1
2
3
4
| for (i = lc; i > 0; i--)
{
cout << c[i];
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#include <string>
using namespace std;
int main()
{
string s1, s2;
int a[100], b[100], c[100] = { 0 };
int i,j,la,lb,lc;
getline(cin, s1);
getline(cin, s2);
la = s1.size();
lb = s2.size();
for (i = 0; i < la; i++)
{
a[la - i] = s1[i] - '0';
}
for (i = 0; i < lb; i++)
{
b[lb - i] = s2[i] - '0';
}
lc = la + lb;
for (i = 1; i <= la; i++)
{
for (j = 1; j <= lb; j++)
{
c[i + j - 1] += a[i] * b[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
while (c[lc] == 0 && lc > 0)
{
lc--;
}
for (i = lc; i > 0; i--)
{
cout << c[i];
}
return 0;
}
|