首页 > 代码库 > n的阶乘结果中一共有多少个零?

n的阶乘结果中一共有多少个零?

题目:n的阶乘中一共有多少个零?
解答:产生零的结果只能有一种可能性那就是2*5=10,然而n的阶乘本质上是可以拆解为很多2和5以及其他不包含2和5的乘数的积,例如5的阶乘:1*2*3*4*5=1*2*3*2*2*5。按照这个思路,将n的阶乘乘积的每一项进行拆解,看看可以拆解出多少个2和多少个5,然后取2的个数和5的个数中最小的即可。程序代码如下:

#include <stdio.h>

int compute_zero(int n)
{
	int five_count = 0;
	int two_count = 0;
	int i, temp;

	for(i = 1; i <= n; i++)
	{
		temp = i;
		while(0 == temp%2) {temp /= 2; two_count ++;}
		temp = i;
		while(0 == temp%5) {temp /= 5; five_count ++;}
	}

	return (five_count > two_count ? two_count : five_count);
}

int compute_answer(int n)
{
	int answer = 1;
	int i;

	for(i = 1; i <= n; i++)
	{
		answer *= i;
		if(answer > 10000000) /*结果中只保留最多6个0*/
		{
			answer %= 10000000;
		}
	}

	return answer;
}

int main()
{
	int n;

	printf("Please input n:");
	scanf("%d", &n);
	printf("answer is: %d.\n", compute_answer(n));
	printf("Answer has zero %d.\n", compute_zero(n));

	return 0;
}
注:实测输入25没有问题,输入的数据过大的时候,compute_answer函数的计算结果可能会出错,本身compute_answer函数的结果也限制了结果的大小主要是显示了后面的低位高位就丢弃掉了,但是根据上面分析的compute_zero结果是不会出错的,这里将两个输出来主要是做一个对比。测试的结果如下所示:


n的阶乘结果中一共有多少个零?