有趣的算法(一)——n阶层尾部有几个0

有趣的算法(一)——n阶层尾部有几个0

(原创内容,转载请注明来源,谢谢)

最近在网上看到好几次这个题目,觉得挺有意思,则准备用PHP进行实现。

1、题目

给一个非负整数n,确定n!的尾部有几个0。

2、输入输出示例

输入 1,输出 0。 输入6,输出1。

3、解

1)最常规的方法,会想到先求解n!,再通过除以10取余数的方式进行。但是此方式求解速度较慢,另外n的值比较大的时候,会产生数据溢出,无法求出n!的值。

代码段如下:

         if(2>$n)$return 0;
         $res= 1;
         for($i=2;$i<=$n;$i++){
         $res *= $i;
}
$zeroNum = 0;
while(0 == $n%10){
         $zeroNum++;
         $n = $n/10;
}
return $zeroNum;

2)由于n! =1*2*3…*n,再分析10=2*5,因此,要确定结尾有几个0,只需要确定n是由多少个2*5组成就行。

观察序列1、2…n,发现明显2的数量远多于5,例如1-10里面,2的因子的数量有8个(其中4=2*2,8=2*2*2)而5的因子只有2个。

因此,要求n!的结尾有几个0,题目就转换成1,2…n共有几个5的因子。该方案有3种求解方式。

1)较慢的求解方式,即遍历1,2..n,把5的因子进行相加

代码段如下:

$fiveNum = 0;
for($i=1;$i<=n;$i++){
         $tmpNum = $i;
         while(1 <= $tmpNum/5){
         $fiveNum++;
         $ tmpNum =floor($tmpNum/5);
}
}
return $fiveNum;

2)稍快的求解方法,分析5的因子的构成,发现5、10、15…等数才有5的因子,因此上述的循环可以改成如下形式。

代码段如下:

$fiveNum = 0;
for($i=5;$i<=n;$i=$i+5){//从5开始遍历,每次步长为5,减少循环次数
         $tmpNum = $i;
         while(1 <= $tmpNum/5){
         $fiveNum++;
         $ tmpNum =floor($tmpNum/5);
}
}
return $fiveNum;

3)更快的求解方法,再对5、10、15…等数字进行分析,发现凡是5的倍数的都有1个5的因子,25的倍数的都有2个5的因子,125的倍数的都有3个5的因子。

因此,将n/5,求得的结果即为5的倍数的个数;再将n除以5,求得的结果是25的倍数的个数,以此类推求解。

代码段如下:

$fiveNum = 0;
while(1 <=$n){
         $fiveNum += $n/5;
         $n = $n/5;
}
return $fiveNum;

——written by linhxx 2017.07.12

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-12

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1732 活蹦乱跳的香穗子

题目描述 香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值 跳的规则是这样的,香穗子可以...

3497
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

2644
来自专栏V站

PHP把二维数组中的值取出组合整一维数组

小伙伴们,之前我们在开发过程中肯定遇到需要把二维数组转换为一维数组的时候,基本上都运用了foreach循环遍历赋值给新数组. 今天这里介绍一个新的方法,通过两个...

1422
来自专栏猿人谷

对快速排序算法的分析

开篇 在实际的过程中,总需要对一些数据进行排序,在众多的排序算法中,快速排序是较为常用的排序算法之一。而网上对于快速排序的中文资料还不是很全。写 这篇博文主要记...

16110
来自专栏木东居士的专栏

Bloom Filter 的基本原理和实现

1454
来自专栏北京马哥教育

看完这篇,你就知道Python生成器是什么

生成器是 Python 初级开发者最难理解的概念之一,虽被认为是 Python 编程中的高级技能,但在各种项目中可以随处见到生成器的身影,你得不得去理解它、使用...

35012
来自专栏技术专栏

基本排序算法

● 基础 ● 编码简单,易于实现,是一些简单情景的首选 ● 在一些特殊情况下,简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为...

572
来自专栏Python小屋

一维序列卷积之Python实现

在数字信号处理中经常会用到卷积计算,例如各种滤波器的设计。两个序列的卷积计算大体需要3步: 1)翻转其中一个序列; 2)移动翻转后的序列,并计算每次移动后两个序...

3139
来自专栏小红豆的数据分析

小蛇学python(16)numpy高阶用法

如果只是从事简单的数据分析,其实numpy的用处并不是很大。简单了解一下numpy,学好pandas已经够用,尤其是对于结构化或表格化数据。但是精通面向数组的编...

722
来自专栏YoungGy

LinearAlgebra_2

列空间和零空间 回顾 主题 例子 AXb 求解AX0 回顾 主题 AX0求解的总体思路 例子 形式化的求解 AXb 什么时候有解 有解的话求解 特解 求出通解 ...

1869

扫描关注云+社区