有趣的算法（一）——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