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

相关文章

来自专栏HansBug's Lab

算法模板——线段树6(二维线段树:区域加法+区域求和)(求助phile)

实现功能——对于一个N×M的方格,1:输入一个区域,将此区域全部值作加法;2:输入一个区域,求此区域全部值的和 其实和一维线段树同理,只是不知道为什么速度比想象...

2865
来自专栏CVer

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

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

802
来自专栏mwangblog

开始使用Octave

1414
来自专栏机器之心

教程 | 在Python和TensorFlow上构建Word2Vec词嵌入模型

选自adventuresinmachinelearning 机器之心编译 参与:李诗萌、刘晓坤 本文详细介绍了 word2vector 模型的模型架构,以及 T...

4207
来自专栏有趣的Python

7- 深度学习之神经网络核心原理与算法-模型的保存与加载

1365
来自专栏null的专栏

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

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

3597
来自专栏企鹅号快讯

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

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

2276
来自专栏xiaoxi666的专栏

最长滑道问题(非递归,C++)

题目描述请参考博客http://blog.csdn.net/sinat_30186009/article/details/52356053,在此表示感谢。

853
来自专栏简书专栏

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

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

1363
来自专栏学习有记

2018 蓝桥杯省赛 B 组模拟赛(五)题目及解析

922

扫码关注云+社区