有趣的算法(一)——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 条评论
登录 后参与评论

相关文章

来自专栏mwangblog

开始使用Octave

2274
来自专栏企鹅号快讯

无人驾驶系列——深度学习笔记:Tensorflow基本概念

随着无人驾驶的火爆,深度学习在无人驾驶中的应用受到广泛关注,我在工作中对此有所接触,因此进行了相关学习和整理,给大家大家可以参考。 ? TensorFlow深度...

2526
来自专栏章鱼的慢慢技术路

Go指南练习_图像

还记得之前编写的图片生成器吗?我们再来编写另外一个,不过这次它将会返回一个 image.Image 的实现而非一个数据切片。

1172
来自专栏xingoo, 一个梦想做发明家的程序员

动态规划基本要素

动态规划性质: 1  最优子结构性质  2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素 1 最优子结构 当问题的最优解包含了其子问题的最优...

21510
来自专栏null的专栏

图解机器学习总结——2、回归

一、回归的定义 image.png 二、最小二乘学习法 image.png 三、最小二乘法实例 对于如下的数据集: ? 画图的代码如下: #coding:UT...

3817
来自专栏简书专栏

基于tensorflow的一元二次方程回归预测

安装tensorflow命令:pip install tensorflow 下面一段代码能够成功运行,则说明安装tensorflow环境成功。

2193
来自专栏祥子的故事

tensorflow | 维度转换

4105
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_纹理图像

玩过游戏的同学们,都知道在游戏人物身上穿的那个叫皮肤,专业点将那个就叫做纹理图像。GLSL 支持在顶点和片段着色器使用纹理图像。

2113
来自专栏WindCoder

TensorFlow入门:一篇机器学习教程

TensorFlow是一个由Google创建的开源软件库,用于实现机器学习和深度学习系统。这两个名称包含一系列强大的算法,它们共享一个共同的挑战——让计算机学习...

3811
来自专栏CVer

TensorFlow从入门到精通 | 01 简单线性模型(上篇)

[TensorFlow从入门到精通] 01 简单线性模型(上)介绍了TensorFlow如何加载MNIST、定义数据维度、TensorFlow图、占位符变量和O...

1062

扫码关注云+社区

领取腾讯云代金券