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

相关文章

来自专栏用户2442861的专栏

最大的子序列和问题

http://blog.csdn.net/zhutulang/article/details/7505785

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

P1410 子序列

题目描述 给定一个长度为N(N为偶数)的序列,问能否将其划分为两个长度为N/2的严格递增子序列, 输入输出格式 输入格式: 若干行,每行表示一组数据。对于每组数...

2626
来自专栏King_3的技术专栏

leetcode-661-Image Smoother

852
来自专栏阮一峰的网络日志

关于颜色理论

我的意思是,我不知道应该选择哪些颜色放在一起,完全凭感觉。于是昨天,我在网上找了一些资料,希望找到理论指导。

672
来自专栏编程之旅

堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写...

873
来自专栏软件开发 -- 分享 互助 成长

C++中巧妙的位运算

位运算要多想到与预算和异或运算,并常常将两个数对应位上相同和不同分开处理 一、x&(x-1)消除x二进制中最右边的一个1。 这个比较厉害,比如统计某个 二、与和...

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

洛谷P2503 [HAOI2006]均分数据(模拟退火)

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

09:图像旋转翻转变换

09:图像旋转翻转变换 总时间限制: 1000ms 内存限制: 65536kB描述 给定m行n列的图像各像素点灰度值,对其依次进行一系列操作后,求最终图像。...

4325
来自专栏PPV课数据科学社区

R语言建立回归分析,并利用VIF查看共线性问题的例子

使用R对内置longley数据集进行回归分析,如果以GNP.deflator作为因变量y,问这个数据集是否存在多重共线性问题?应该选择哪些变量参与回归? 答: ...

3678
来自专栏机器学习算法全栈工程师

经典算法题之Maximal Square

作者:叶 虎 编辑:邓高锦 Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题,同时也是2017京东面试题,2016华为机考题...

3679

扫码关注云+社区