【正确答案】方法一:蛮力法
最简单的方法就是计算出1024!的值,然后判断末尾有多少个0,但是这种方法有两个非常大的缺点:第一,算法的效率非常低下;第二,当这个数字比较大的时候直接计算阶乘可能会导致数据溢出,从而导致计算结果出现偏差。因此,下面给出一种比较巧妙的方法。
方法二:因子法
5与任何一个偶数相乘都会增加末尾0的个数,由于偶数的个数肯定比5的个数多,因此,1~1024所有数字中有5的因子的数字的个数决定了1024!末尾0的个数。因此,只需要统计因子5的个数即可。此外5与偶数相乘会使末尾增加一个0,25(有两个因子5)与偶数相乘会使末尾增加两个0,125(有三个因子5)与偶数相乘会使末尾增加3个0,625(有四个因子5)与偶数相乘会使末尾增加四个0。对于本题而言:
是5的倍数的数有:a1=1024/5=204个;
是25的倍数的数有:a2=1024/25=40个(a1计算了25中的一个因子5);
是125的倍数的数有:a3=1024/125=8个(a1,a2分别计算了125中的一个因子5);
是625的倍数的数有:a4=1024/625=1个(a1,a2,a3分别计算了625中的一个因子5)。
所以,1024!中总共有a1+a2+a3+a4=204+40+8+1=253个因子5。因此,末尾总共有253个0。根据以上思路实现代码如下:
def zeroCount(n):
count=0
while n>0:
n=n/5
count+=n
return count
if __name__=="__main__":
print "1024!末尾0的个数为: "+str(zeroCount(1024))
程序的运行结果为:
1024!末尾0的个数为:253
算法性能分析:
由于这种方法循环的次数为n/5,因此算法时间复杂度为O(n)。
【答案解析】[考点] 如何判断1024!末尾有多少个0