大数运算

前言

大数运算的阶乘与乘法问题。


大数运算的核心思想是用一个数组来代替一个非常大的数。乘法的过程类似手工竖乘。

阶乘

用一个数组记录结果。

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
void bigFact(int n)
{
vector<int> a(1000, 0);
a[0] = 1;
int carry = 0;
int digits = 1;//记录有效的数字位数
for (int i = 2; i <= n;i++)
{
int j = 0;
for (carry = 0; j < digits; j++)//从低位开始,每一位乘上i
{
int tmp = a[j] * i+carry;
a[j] = tmp % 10;
carry = tmp / 10;
}
while (carry)
{
a[++digits - 1] = carry % 10;
carry /= 10;
}
}
for (int i = digits-1; i >=0; i--)
{
cout << a[i];
}
}

乘法

需要用两个数组记录两个乘数,和一个res数组记录结果。进位在每位相乘之后进行。最后要处理结果前面的0。

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
void bigMul()
{
string a, b;
vector<int>x, y,res;
int i, j;
while (cin>>a>>b)
{
int lena = a.size();
int lenb = b.size();
x.resize(lena, 0);
y.resize(lenb, 0);
res.resize(lena + lenb, 0);

for (i = 0; i < lena; i++)
{
x[lena - 1 - i] = a[i] - '0';
}
for (j = 0; j < lenb; j++)
{
y[lenb - 1 - j] = b[j] - '0';
}
for (i = 0; i < lena; i++)
{
for (int j = 0; j < lenb; j++)
res[i + j] += x[i] * y[j];
}
int carry = 0;
for (i = 0; i < res.size(); i++)
{
int tmp = carry + res[i];
carry = tmp / 10;
res[i] = tmp % 10;
}
for (i = res.size()-1; i >= 0; i--)
{
if (res[i] != 0)break;
}
for (j = i; j >= 0; j--)
cout << res[j];
}
}

可以利用分治策略达到更快的效率。

您的支持是我创造源源不断地动力