1024!末尾有几个0

1024!末尾有几个0

2016-03-20 01:41:22  回复(2108  分享

上周做了一道算法题:计算1024!末尾有几个0。其实挺简单,然而当时脑子一时短路没做出来,回来后好好整理了一下思路,尝试解开它。

首先,绝对不可能写个循环把1乘到1024,这是一个大数乘法,计算起来效率太低,那么只能尝试从其他方面来入手了。

先分析,乘积末尾出现0的次数必然取决于乘数里10的倍数的数量(以及乘积为10的倍数的乘数),那么好办,我们只需要列举出从1到1024中有多少个10的倍数(10,20,30等),以及有多少个乘积为10的倍数的乘数。

分析很容易得出,只有5的倍数乘以偶数才可能出现乘积为10的倍数,那么简单,我们只需要统计有多少个5的倍数以及偶数就行了。

继续分析,从1到1024的这个等差数列里,5的倍数有floor(1024 / 5)=204个,而偶数有floor(1024/2)=512个,明显偶数比5的倍数多,那么所有的5的倍数都必然产生0。

好了,现在我们知道了1024!末尾0的数量与1至1024数列中5的倍数的数量成正相关,那么一个5的倍数可能产生多少个0呢?

再来想想:10 * x末尾有1个0(x不为10的倍数),而100x末尾则有两个0,以此类推10^n * x末尾有n个0,而10=5*2,那么10^n就是5^n * 2 ^ n。如上所述,差距为1的等差数列里2^n必然比5^n多,那么我们就可以大胆地假设该阶乘中5^n的倍数必然产生n个0。

那么事情就好办了,我们只需要从数列里挑出所有的5的倍数,并记录数量,再从这些5的倍数的数字里查找5^2的倍数,以此类推直到统计出所有的0。

于是开始写代码了:

$number = 1024;

$zeroSum = 0;

// 该循环从5循环到$number,每次+5

// 循环次数既是5的倍数的数量

for($i = 5; $i <= $number; $i+=5){

$zeroSum++; // 每个5的倍数必然产生1个0

if($i % 25 != 0){// 如果当前循环值不是25的倍数,那就不需要验证下面的了

continue;

}

$currentNumber = $i / 5;

// 重复将该数除以5,看是否5的倍数,如果是则继续+1

while(true){

if($currentNumber % 5 != 0){

break;

}

$zeroSum++;

$currentNumber /= 5;

}

}

echo($zeroSum);

这代码思路很简单,先把1到1024的所有5的倍数列举出来,然后逐个除以5再判断是否5的倍数,是的话再加1。

到这里,1024!末尾有多少个0答案已经出来了,总共是253个。

不过想想,似乎这个算法的效率有些低,继续做分析。

我们知道,1到1024总共有floor(1024 / 5)个5的倍数,同理,这floor(1024 / 5)个5的倍数里必有floor(floor(1024 / 5) / 5)个5^2的倍数,以此类推。

那么可以尝试用递归来解决问题,开始编写以下代码:

$number = 1024;

echo(getMultipleOf5($number));

function getMultipleOf5($number){

// 统计$number中有多少个5的倍数,如果为0,则直接返回0

$nextNumber = floor($number / 5);

if($nextNumber == 0){

return $nextNumber;

}

// 如果$number中5的倍数不为0,那么递归到下一层进行统计

return $nextNumber + getMultipleOf5($nextNumber);

}

这次代码更简洁,这个也是该题的标准答案,百度搜索一下“1024!末尾有多少个0”能找到一模一样的算法(但实现的语言不一样)。

简单解释一下,如上所说,阶乘的数列里5 * x能对结果的末尾产生1个0,5^2 * x能产生2个0,那么我们先执行一次getMultipleOf5函数,获取该数列里所有5的倍数$nextNumber,当然,$nextNumber个5的倍数里必然有floor(nextNumber / 5)个5^2的倍数,而5^2的倍数的数字必然在结果末尾额外产生一个0。那么我们就进行递归,继续统计$nextNumber个5的倍数的数字中有多少个5^2的倍数,递归不断深入,直至不可执行为止(找到5^n最大的n值),并将结果全部加起来,就是我们要的答案。

表述可能有些不清晰,思路大致是这样。最近一直在看算法导论,突然发现自己写了十多年的程序,算法却是一片空白,实在有些不妥,其实很多算法都可以通过高中知识来解决,然而高中因为不爱学习,数学一直很渣,现在多少还是挺后悔。还是多锻炼一下自己的数学思维吧。

评论

发表评论:

*您的昵称:
*评论内容:
*您的性别:   
您的Email: (可选,您的留言被回复后用于提醒,不公开)