如何计算阶乘运算结果尾部有多少个零

Write an algorithm which computes the number of trailing zeros in n factorial.

阶乘n! = n*(n-1)*...*1

要计算出这样的运算结果有多少个零，如果直接运算就很可能是溢出，那么只能用其他方法了。

因为尾零得来是由于2*5等于10，那么就会为结果增加一个零，所以只要计算这两个数出现了多少对就可以了。但是由于2出现的次数会远远大于5，所以，只要计算5的倍数出现多少次。

程序本身很好理解，就是如何想出来的确是个麻烦。

老实说，我也是参考书上的分析再写出来的，具体需要怎么样才能想出来，我觉得就需要举例子，然后观察，最后总结出规律，难度还是很大的。

书中说：By thinking through what exactly will contribute a zero ,you can come up with a solution.

程序1：

int factorialZero(int n)
{
	if (n < 0)
	{
		return -1;
	}
	int fiveNums = 0;
	//注意：这里是i<=n
	for (int i = 5; i <= n; i+=5)
	{
		//注意：这里必须要定义一个j，否则会改变了i的值，使得结果不正确的。
		int j = i;
		while (j%5 == 0)
		{
			fiveNums++;
			//注意：这里是要这样计算
			j /= 5;
		}
	}
	return fiveNums;
}

程序2：

int factorFive(int n)
{
	int c = 0;
	while (n%5 == 0)
	{
		c++;
		n /= 5;
	}
	return c;
}

int factorialZero2(int n)
{
	if (n < 0)
	{
		return -1;
	}
	int fiveNums = 0;
	for (int i = 5; i <= n; i+=5)
	{
		fiveNums += factorFive(i);
	}
	return fiveNums;
}

程序3，这个优化了的程序就更加难以想象出来了。举个例子就能知道它是如何计算的了。

int improFactoriaolZero(int n)
{
	if (n < 0)
	{
		return -1;
	}
	int fiveNums = 0;
	for (int i = 5; n/i > 0; i*=5)
	{
		fiveNums += n/i;
	}
	return fiveNums;
}

主测试程序：

int main()
{
	cout<<"factorialZero(25-55):\n";
	for (int i = 25; i <= 55; i++)
	{
		cout<<factorialZero(i)<<" ";
	}
	cout<<endl;
	cout<<"factorialZero2(25-55):\n";
	for (int i = 25; i <= 55; i++)
	{
		cout<<factorialZero2(i)<<" ";
	}
	cout<<endl;
	cout<<"improFactorialZero(25-55):\n";
	for (int i = 25; i <= 55; i++)
	{
		cout<<improFactoriaolZero(i)<<" ";
	}
	cout<<endl;
		
	system("pause");
	return 0;
}

运行结果，计算了25阶乘，一直到55阶乘的尾零分别为多少：