在数学中，正整数的阶乘（Factorial）被定义为所有小于及等于该数的正整数的积，其数学表示为$n!=1 \times 2 \times 3 \times … \times n$，同时，定义$0!=1$，$1!=1$。当$n$比较小时，可以很方便地借助递归函数，求得其阶乘值，比如：
1
2
3
4
5
6
7
| class Solution {
public:
unsigned long factorial(int n)
{
return (n > 1) ? n * factorial(n - 1) : 1;
}
};
|
然而，当$n$比较大时，其阶乘值极大，不容易通过上述递归函数求得，比如：
1
2
3
4
5
6
7
8
9
| Input: 100
Output: 933262154439441526816992388562667004-
907159682643816214685929638952175999-
932299156089414639761565182862536979-
208272237582511852109168640000000000-
00000000000000
Input: 50
Output: 3041409320171337804361260816606476884-
4377641568960512000000000000
|
因此，必须考虑新的方法。我们可以定义一个大小为MAX的数组，即res[MAX]，而后令正整数x乘以res[X]，并更新res[X]的值，比如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # 存在一个正整数36，其表示方法为：
res[] = [6, 3] # size = 2
# 存在因数2
x = 2
# 初始化
carry = 0
# stop iff i == 2
i = 0, product = res[0] * x + carry = 12 => res[0] = 2, carry = 1
i += 1
# update
i = 1, product = res[1] * x + carry = 7 => res[1] = 7, carry = 0
res[] = [2, 7]
|
于是，对于大数的阶乘算法，以C++代码表示：
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
| #include <string>
#define MAX 500
using namespace std;
int multiply(int i, int res[], int res_size) {
int carry = 0;
for (int k = 0; k < res_size; ++k) {
int prod = res[k] * i + carry;
res[k] = prod % 10;
carry = prod / 10;
}
while (carry) {
res[res_size] = carry % 10;
carry = carry / 10;
res_size++;
}
return res_size;
}
string factorial(int factorial) {
int res[MAX];
string out;
res[0] = 1;
int res_size = 1;
for (int i = 2; i <= factorial; ++i) {
res_size = multiply(i, res, res_size);
}
for (int j = res_size - 1; j >= 0; --j) {
out += to_string(res[j]);
}
return out;
}
|
原题来源：Codewars - Large Factorials