算一算N阶乘的尾随零个数
算一算N阶乘的尾随零个数
问题描述很简单: 求解N阶乘的尾随零个数
而所谓尾随零个数,即是从个位数开始,数字连续为0的个数. 譬如:
3!(阶乘符号,下同) = 3 * 2 * 1 = 6, 尾随零个数为0
5! = 5 * 4 * 3 * 2 * 1 = 120, 尾随零个数为1
10! = 10 * 9 * … * 1 = 3628800, 尾随零个数为2
OK,明白问题之后,我们就来尝试算一算吧~
方法1
既然要求解阶乘值的尾随零个数,直观的方法就是首先算出阶乘值,然后对10取模来计算尾随零个数,代码如下:
function factorial(n)
local val = 1
for i = 2, n do
val = val * i
end
return val
end
function trailing_zero_count(value)
local count = 0
while value % 10 == 0 do
count = count + 1
value = value / 10
end
return count
end
function factorial_trailing_zero_count(n)
local value = factorial(n)
return trailing_zero_count(value)
end方法2
方法1简单直观,但是当所求N阶乘较大时容易造成乘法溢出(譬如N=40),一种方法是使用大数运算来解决溢出问题;另外一种更轻量的方法则是直接从尾数零的性质入手:
考虑一下,一个数字A如果有一个尾数零,其实就是意味着A有一个10因子,如果有两个尾数零,则说明A有两个10因子(即有一个 10 * 10 = 100 因子),以此类推~
所以我们只要知道了N阶乘有多少个10因子就知道了N阶乘有多少个尾数零,这里我们不能直接计算N阶乘的大小(还记的之前那个溢出问题吗),而是要通过N阶乘的定义(或者其他方式)来直接计算~
这里我们需要一点技巧:
首先我们对10进行一下素数分解
10 = 2 * 5
而
N! = N * (N - 1) * (N - 2) * … * 1
假设我们能求出某个数字A中2因子的个数,求解的方法设为
factor_2_count(A)
相似的,我们设求解某个数B中5因子的个数方法为
factor_5_count(B)
那么有:
factor_2_count(N!) = factor_2_count(N) + factor_2_count(N - 1) + factor_2_count(N - 2) + … + factor_2_count(1)
factor_5_count(N!) = factor_5_count(N) + factor_5_count(N - 1) + factor_5_count(N - 2) + … + factor_5_count(1)
又由于
10 = 2 * 5 (一个2因子和一个5因子构成一个10因子)
所以N!的10因子个数(即尾数零个数)为:
min(factor_2_count(N!), factor_5_count(N!)) (min为最小值函数)
相关代码如下:
function factor_2_count(n)
local count = 0
while n % 2 == 0 do
count = count + 1
n = n / 2
end
return count
end
function factorial_factor_2_count(n)
local count = 0
for i = 1, n do
count = count + factor_2_count(i)
end
return count
end
function factor_5_count(n)
local count = 0
while n % 5 == 0 do
count = count + 1
n = n / 5
end
return count
end
function factorial_factor_5_count(n)
local count = 0
for i = 1, n do
count = count + factor_5_count(i)
end
return count
end
function factorial_trailing_zero_count_v2(n)
return math.min(factorial_factor_2_count(n), factorial_factor_5_count(n))
end方法3
考虑方法2的解法步骤,我们分别计算了N阶乘中因子2的个数和因子5的个数,但实际上,N阶乘中因子2的个数一定是大于等于因子5的个数的(数学归纳法应该是证明的一种方法),即:
factor_2_count(N!) >= factor_5_count(N!)
所以有:
min(factor_2_count(N!), factor_5_count(N!)) = factor_5_count(N!)
这也意味着实际上我们只需要计算N阶乘中因子5的个数就可以了~
代码如下:
function factor_5_count(n)
local count = 0
while n % 5 == 0 do
count = count + 1
n = n / 5
end
return count
end
function factorial_factor_5_count(n)
local count = 0
for i = 1, n do
count = count + factor_5_count(i)
end
return count
end
function factorial_trailing_zero_count_v3(n)
return factorial_factor_5_count(n)
end方法4
方法4的理解难度相对就比较高了,考虑数n1:
n1 = N / 5
他表示的是1到N中带有因子5的数字的个数
但根据方法3中的讲述,我们需要求的是1到N中所有因子5的个数
怎么通过n1这种计算方式来计算因子5的总数呢?
考虑数n2:
n2 = N / (5 * 5) = N / 25
他表示的是1到N中带有因子25的数字的个数
则 n1 + n2 就代表1到N(N < 125)中所有因子5的个数,对于更大的N,我们需要继续计算(这里理解有些难度,不明白的同学可以多想一想~):
n3 = N / (5 * 5 * 5) = N / 125
n4 = N / (5 * 5 * 5 * 5) = N / 625
…
然后通过计算
n1 + n2 + n3 + n4 + …
来计算1到N中所有因子5的个数~
代码如下:
function factorial_trailing_zero_count_v4(n)
local count = 0
local factor = 5
while n >= factor do
count = count + math.floor(n / factor)
factor = factor * 5
end
return count
end还有其他方法!?有知道的朋友可以告知下~
OK,我们下次再见吧~