/************************************************************
算法思想：在1-10兩個數相乘要產生0，只有 10×1=2×5，2×5。
200！=200×199×198……×2×1=2×5×2×5×2×199…. ×2×1;可以分解為質數相乘的形式,
很明顯有2的個數比5的多,所以只要求出200的階乘可分解出多少個5相乘,
就可得到200的階乘結尾的連續的零的個數.
即:num=[200/5]+[200/5/5]+[200/5/5/5].
注: [x]表示對x取整.
所以可以通過這個思路很容易的得到任意階乘結尾連續的零，其示例C語言代碼如下：
*************************************************************/
#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
using namespace std;
#define MAX 100
//MAX 是計算結果的最大位數 取為100位
void factorial(int n,char output[])
{
int i, j, cin, tmp;
int result[MAX];
memset(result, 0, sizeof(result)); //初始化為0
result[0] = 1;
for(i = 2; i <= n; ++i) //從2 開始計算階乘
{
cin = 0; //進位初始化為0
for(j = 0; j < MAX; ++j)
{
tmp = result[j] * i + cin; //cin進位
result[j] = tmp % 10;
cin = tmp / 10;
}
}
for(i = MAX - 1; i >= 0; --i) //忽略前導的0
if(result[i]) break;
for(j = i; j >= 0; j--) //將結果倒敘打印在結果數組中
sprintf(output++,"%d", result[j]);
//注意sprintf的第一個參數是char型指針
}
/*計算n!結尾零的個數，返回結尾零的個數。*/
int GetZeroNum(int n)
{
int num=0;//n!結尾零的個數
int b=1;//5的次方
while(1)
{
b*=5;
num+=n/b;
if(b>n)
break;
}
return num;//返回結尾零的個數
}
int main()
{ char out[MAX]={0};
int i=5;
factorial(i,out);
cout<<"factorial("<<i<<") is "<<out<<endl;
cout<<"factorial("<<i<<") the number of 0 in the rear is "<<GetZeroNum(i)<<endl;
i=10;
factorial(i,out);
cout<<"factorial("<<i<<") is "<<out<<endl;
cout<<"factorial("<<i<<") the number of 0 in the rear is "<<GetZeroNum(i)<<endl;
i=20;
factorial(i,out);
cout<<"factorial("<<i<<") is "<<out<<endl;
cout<<"factorial("<<i<<") the number of 0 in the rear is "<<GetZeroNum(i)<<endl;
i=30;
factorial(i,out);
cout<<"factorial("<<i<<") is "<<out<<endl;
cout<<"factorial("<<i<<") the number of 0 in the rear is "<<GetZeroNum(i)<<endl;
}
/********************************
factorial(5) is 120
factorial(5) the number of 0 in the rear is 1
factorial(10) is 3628800
factorial(10) the number of 0 in the rear is 2
factorial(20) is 2432902008176640000
factorial(20) the number of 0 in the rear is 4
factorial(30) is 265252859812191058636308480000000
factorial(30) the number of 0 in the rear is 7
Process returned 0 (0x0) execution time : 0.109 s
Press any key to continue.
********************************/
