阶乘(Factorial)函数
计算某数(正整数)的阶乘,是指计算所有小于及等于该数的正整数的积。方程式表示如下:
#{{{
\begin{alignedat}{2}
Factorial(n) &{}={}&& n! \\
&{}={}&& 1 \times 2 \times 3 \times \dotsb \times (n - 1) \times n \\
&{}={}&& [1 \times 2 \times 3 \times \dotsb \times (n - 1)] \times n \\
&{}={}&& n \times (n - 1)!
\end{alignedat}
}}}#
且定义
#{{{
0! = 1
}}}#
我们可以很直觉地写出如下的递归程序:
Rust
Java
TypeScript
Go
pub fn factorial(n: u8) -> u128 {
if n <= 1 {
1
} else {
n as u128 * factorial(n - 1)
}
}
public static long factorial(final byte n) {
if (n <= 1) {
return 1;
} else {
return n * factorial((byte)(n - 1));
}
}
function factorial(n: number) {
if (n <= 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
func Factorial(n uint8) uint64 {
if n <= 1 {
return 1
} else {
return uint64(n) * Factorial(n-1)
}
}
阶乘的数值大小成长得很快,以下分别列出不同比特的无号整数所能保存的最大阶乘值:
32 比特:12!
64 比特:20!
128 比特:34!
256 比特:57!
非递归的阶乘函数
以递归的方式调用函数,每次都需要创建新的堆栈框(Stack Frame),堆栈框的数量太多就会导致堆栈溢出(Stack Overflow),所以在实际应用上我们会比较偏好不去使用递归函数。上面的阶乘递归函数,可以参考以下文章来转成非递归的版本:
转换后的非递归阶乘函数如下:
Rust
Java
TypeScript
Go
pub fn factorial(n: u8) -> u128 {
let mut accumulator = 1u128;
for i in 2..=n as u128 {
accumulator *= i;
}
accumulator
}
public static long factorial(final byte n) {
long accumulator = 1;
for (byte i = 2; i <= n; ++i) {
accumulator *= i;
}
return accumulator;
}
function factorial(n: number) {
let accumulator = 1;
for (let i = 2;i <= n;i++) {
accumulator *= i;
}
return accumulator;
}
func Factorial(n uint8) uint64 {
accumulator := uint64(1)
for i := uint8(2); i <= n; i++ {
accumulator *= uint64(i)
}
return accumulator
}
阶乘的大数运算
要实作阶乘的大数运算,只要会乘法的大数运算即可。可以参考以下文章来了解加减乘除的大数运算:
N! 有几位数?
前面提到阶乘的数值大小成长得很快,那它到底会有几位数呢?
要求出数字 #{{N}}# 有几位数,我们可以用下面这个公式来直接算出:
#{{{
\lfloor {log_{10}N} \rfloor + 1
}}}#
所以,#{{N!}}# 有几位数,可以这样计算:
#{{{
\begin{alignedat}{2}
&&&\lfloor {logN!} \rfloor + 1 \\
&{}={}&& \lfloor {log(1 \times 2 \times 3 \times \dotsb \times N)} \rfloor + 1 \\
&{}={}&& \lfloor {log1 + log2 + log3 + \dotsb + logN} \rfloor + 1
\end{alignedat}
}}}#
程序实作如下:
Rust
Java
TypeScript
Go
pub fn count_factorial_digits(n: u32) -> u32 {
let mut sum = 0.0;
for i in 2..=n {
sum += (i as f64).log10();
}
sum.floor() as u32 + 1
}
public static int countFactorialDigits(final int n) {
double sum = 0.0;
for (int i = 2; i <= n; i++) {
sum += Math.log10(i);
}
return (int)Math.floor(sum) + 1;
}
function countFactorialDigits(n: number) {
let sum = 0.0;
for (let i = 2;i <= n;i++) {
sum += Math.log10(i);
}
return Math.floor(sum) + 1;
}
func CountFactorialDigits(n uint32) uint32 {
sum := 0.0
for i := uint32(2); i <= n; i++ {
sum += math.Log10(float64(i))
}
return uint32(math.Floor(sum)) + 1
}
由于 #{{log1 = 0}}#,所以计次循环从 2 开始。
上面程序的时间复杂度为 #{{O(N)}}#,其实还可以更快,快到 #{{O(1)}}#。
史特灵公式(Stirling's formula),是用来计算阶乘近似值的公式,如下:
#{{{
n! \approx {\sqrt{2 \pi n}}{({n \over e})}^n
}}}#
虽然史特灵公式只是近似公式,但要拿它来计算阶乘的位数已经足够准确了,只不过 #{{N}}# 小于 #{{2}}# 的时候要另外处理(#{{0!}}# 和 #{{1!}}# 都是 #{{1}}#,只有 1 位数)。位数的计算方式如下:
#{{{
\begin{alignedat}{2}
&&&\lfloor {logN!} \rfloor + 1 \\
&{}\approx{}&& \lfloor {log({\sqrt{2 \pi N}}{({N \over e})}^N)} \rfloor + 1 \\
&{}={}&& \lfloor { {1 \over 2}log(2 \pi N) + Nlog({N \over e}) } \rfloor + 1 \\
&{}={}&& \lfloor { {1 \over 2} \times [log(2 \pi) + logN] + N \times [logN - log(e)] } \rfloor + 1
\end{alignedat}
}}}#
程序实作如下:
Rust
Java
TypeScript
Go
pub fn count_factorial_digits(n: u32) -> u32 {
if n < 2 {
return 1;
}
let log_2_pi = (2.0 * std::f64::consts::PI).log10();
let n_f64 = n as f64;
let log_n = n_f64.log10();
(0.5 * (log_2_pi + log_n) + n_f64 * (log_n - std::f64::consts::LOG10_E)).floor() as u32 + 1
}
private static final double LOG_E = Math.log10(Math.E);
private static final double LOG_2_PI = Math.log10(2.0 * Math.PI);
public static int countFactorialDigits(final int n) {
if (n < 2) {
return 1;
}
final double logN = Math.log10(n);
return (int)Math.floor(0.5 * (LOG_2_PI + logN) + n * (logN - LOG_E)) + 1;
}
const LOG_2_PI = Math.log10(2.0 * Math.PI);
function countFactorialDigits(n: number) {
if (n < 2) {
return 1;
}
const logN = Math.log10(n);
return Math.floor((0.5 * (LOG_2_PI + logN)) + (n * (logN - Math.LOG10E))) + 1;
}
func CountFactorialDigits(n uint32) uint32 {
if n < 2 {
return 1
}
log2Pi := math.Log10(2.0 * math.Pi)
nF64 := float64(n)
logN := math.Log10(nF64)
return uint32(math.Floor(0.5*(log2Pi+logN)+nF64*(logN-math.Log10E))) + 1
}
N! 的尾端有几个 0?
阶乘是连续的正整数相乘所得的结果,什么情况下尾端会多出一个 0?那就是 #{{2 \times 5}}# 的时候啦!N! 的质因数中有几组 2 和 5,N! 的尾端就会有几个 0。由于 2 的数量肯定不会比 5 的数量少,所以我们只需要去计算 N! 在质因数分解后有几个 5,就是尾端的 0 的数量。
以下公式可以算出 N! 在质因数分解后有几个 5:
#{{{
\lfloor {N \over 5} \rfloor + \lfloor {N \over 25} \rfloor + \lfloor {N \over 125} \rfloor + \dotsb + \lfloor {N \over 5^i} \rfloor, 5^i \leq N
}}}#
例如,#{{4! = 24}}#,尾端有 0 个 0;#{{5! = 120}}#,尾端有 1 个 0;#{{9! = 362880}}#,尾端有 1 个 0;#{{10! = 3628800}}#,尾端有 2 个 0;#{{24! = 620448401733239439360000}}#,尾端有 4 个 0;#{{25! = 15511210043330985984000000}}#,尾端有 6 个 0。
在用程序实作之前,可以将上面的式子写成以下这样,会更容易实作:
#{{{
\lfloor {N \over 5} \rfloor + \lfloor {{N \over 5} \over 5} \rfloor + \lfloor {{{N \over 5} \over 5} \over 5} \rfloor + \dotsb
}}}#
当最外层的分子小于 5 时,就可以不用再加下去了,因为只会取整数部份来相加。
程序实作如下:
Rust
Java
TypeScript
Go
pub fn count_factorial_tail_zeros(mut n: u32) -> u32 {
let mut sum = 0;
while n >= 5 {
n /= 5;
sum += n;
}
sum
}
public static int countFactorialTailZeros(int n) {
int sum = 0;
while (n >= 5) {
n /= 5;
sum += n;
}
return sum;
}
function countFactorialTailZeros(n: number) {
let sum = 0;
while (n >= 5) {
n = Math.floor(n / 5);
sum += n;
}
return sum;
}
func CountFactorialTailZeros(n uint32) uint32 {
sum := uint32(0)
for n >= 5 {
n /= 5
sum += n
}
return sum
}