算一算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,我们下次再见吧~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

快速傅里叶变换(FFT)详解

本文只讨论FFT在信息学奥赛中的应用 文中内容均为个人理解,如有错误请指出,不胜感激 前言 先解释几个比较容易混淆的缩写吧 DFT:离散傅里叶变换—> 计算多...

4727
来自专栏利炳根的专栏

学习笔记DL004:标量、向量、矩阵、张量,矩阵、向量相乘,单位矩阵、逆矩阵

线性代数,面向连续数学,非离散数学。《The Matrix Cookbook》,Petersen and Pedersen,2006。Shilov(1977)。

3960
来自专栏CreateAMind

keras doc 9 预处理等

用以生成一个batch的图像数据,支持实时数据提升。训练时该函数会无限生成数据,直到达到规定的epoch次数为止。

2562
来自专栏转载gongluck的CSDN博客

bmp图像大小biSizeImage算法公式由来

LPBITMAPINFOHEADER lpbmiHeader; // ... 计算BMP方法 法一:lpbmiHeader->biSizeImage = (cx...

5035
来自专栏人工智能LeadAI

机器学习实战 | 第二章:线性回归模型

线性回归(Linear Regression) 这个类是传统最小二乘回归的类.是最基础的线性回归的类. class sklearn.linear_model....

3217
来自专栏余林丰

12.高斯消去法(1)——矩阵编程基础

对于一阶线性方程的求解有多种方式,这里将介绍利用高斯消去法解一阶线性方程组。在介绍高斯消去法前需要对《线性代数》做一下温习,同时在代码中对于矩阵的存储做一个简...

2497
来自专栏人工智能

十五:多层感知机与布尔函数

今天没有别的话,好好学习,多多转发! 本期内容是 【多层感知机与布尔函数】 场景描述 神经网络概念的诞生很大程度上受到了神经科学的启发。生物学研究表明,大脑皮层...

3138
来自专栏C语言及其他语言

训练场优秀题解-尼科彻斯定理【图文并茂】

原题链接:【C语言训练】尼科彻斯定理 http://www.dotcpp.com/oj/problem1127.html 解题思路: 首先,定义整数N;写出N从...

3209
来自专栏悦思悦读

分类模型的评价指标:Precision,Recall和Accuracy

既然要判断程度,就必然会用到能够描述“多少”的数值型指标。今天我们就要介绍几种分类模型最常用的评价指标。

1734
来自专栏C语言及其他语言

【每日一题】问题 1432:剪格子

历届试题 剪格子 时间限制:1.0s 内存限制:256.0MB 问题描述 如下图所示,3 x 3 的格子中填写了一些整数。 +--...

712

扫码关注云+社区

领取腾讯云代金券