现在的位置: 首页 > 综合 > 正文

1024!末尾有几个零?

2013年09月08日 ⁄ 综合 ⁄ 共 632字 ⁄ 字号 评论关闭

以前见过这题几次,也不记得是哪里的面试题了。

1024可计为N

解题方法有两种:

一、使用大整数运算,也算是“暴力求解”了。但只看可能的求解长度就下一跳啊。此法不可取。

二、运用数学理论不难发现:

1、结果0的个数是和其小于N中各位为5的个数不无关系的。不是5的倍数无论和哪个相乘都不可能出现个位为0的结果。

N以内的偶数个数肯定是大于5倍数的个数的(5和偶数相乘才可能增加末位0的个数)。

所以有a = N / 5;

2、再看一下25这个是不是有点特殊呢?25 * 4 = 100,能产生两个0,这是为什么呢?因为25 = 5 * 5;因为能产生多余0的个数是和包含因子5的个数相关的。

25 * 4 = 100,有两个0,100无论在和任何非10倍数的数相乘都不可能产生多余两个0的数。同理(75 = 25 * 3 = 5 * 5 *3)* 4 = 300;(125 = 5 * 5 * 5 )* 8 = 1000;

即一个数包含多少个因子5其就可以同足够的偶数相乘产生相同个数的末位0。

总结如下:N的阶乘中末位0的个数为:N/5 + N/25 + N/125 ……

计算测试程序:

#include <stdio.h>

int zero_count(int n);

int main(int argc ,char *argv[])
{
	printf("zero_count is %d...\n", zero_count(1024));
	return 0;
}

int zero_count(int n)
{
	int count = 0;
	while(n > 0) {
		n = n/5;
		count += n;
	}
	return count;
}

抱歉!评论已关闭.