算一算N阶乘的尾随零个数

r囧r小猫 2022-05-23 07:34 184阅读 0赞

问题描述很简单: **求解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**),一种方法是使用[大数运算][Link 1]来解决溢出问题;另外一种更轻量的方法则是直接从尾数零的性质入手:

考虑一下,一个数字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,我们下次再见吧~

[Link 1]: https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic