56、php实现N的阶乘末尾有多个0
题目： php实现N的阶乘末尾有多个0描述：
阶乘
N! = 123*…N;
比如 5! = 12345 = 120 末了有1个0
解题思绪：
N! = K*(10^M)
N的阶乘为K和10的M次方的乘积，那么N!末尾就有M个0。如果将N的阶乘分解后，那么N的阶乘可以分解为： 2的X次方，3的Y次方，4的Z次方，…的乘积。
由于10 = 2 * 5,以是M只能和X和Z有关，每一对2和5相乘就可以得到一个10，
于是M = MIN( X,Z),不难看出X大于Z，
因为被2整除的频率比被5整除的频率高的多。以是可以把公式简化为M=Z
以是我们求解N的阶乘末了的0.相当于求解里面有多个5的因子
当我们遇到一大题目可以拆成一个个小的题目，来求解。
function factorial($n)
{
$n = intval($n);
if ($n < 0) {
return 0;
}
$sum = 0;
for ($i = 5; $i <= $n; $i = $i + 5) {
$j = $i;
//求解5的个数 比如15 里面有3个5
while ($j % 5 == 0) {
$sum++;
$j = $j / 5;
}
}
return $sum;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]