阶乘算法之一N! 末尾有多少个零 博客分类： java 服务 java阶乘算法面试效率
题：给定一个整数N，求出N!末尾有多少个零，比如N=10，N!=3628800，10！末尾有两个零。
首先温固一下阶乘的相关知识！
阶乘(factorial)是基斯顿·卡曼(Christian Kramp, 1760 – 1826)于1808年发明的运算符号。阶乘，也是数学里的一种术语。
任何大于1的自然数n阶乘表示方法：n!=1×2×3×……×n 或n!= n×(n-1)!
0！=1，注意(0的阶乘是存在的).
双阶乘：
当n为奇数时表示不大于n的所有奇数的乘积 如：7!!=1×3×5×7
当n为偶数时表示不大于n的所有偶数的乘积(除0外） 如：8!!=2×4×6×8
小于0的整数-n的阶乘表示：
（-n）！= 1 / (n+1)!
双阶乘是怎么提出来的，是根据阶乘推导出来的吗？这点百思不解？
N个自然数相乘，结尾0的个数，依赖有多少个10相乘（有两个10相乘，结尾0的个数就为2），10=2×5，则可以理解为结尾0的个数依赖因子中2的个数和5的个数，而对于连续的自然数来说，2出现的频率比5高的多，所以最终只需要计算出因子中5的个数，即为答案。
把想法整理为JAVA代码，如下所示：
解题思路一：分析阶乘因子中的每一个数，计算其包含5的个数，最后求总和
private int zeroNum(int n){
int ret = 0;
for(int i=1;i<=n;i++){
int j=i;
while(j%5 == 0){
ret++;
j/=5;
}
}
return ret;
}
时间复杂度为：Nlog5N
解题思路二：
令f(x)表示正整数x末尾所含有的“0”的个数，则有：
当0 < n < 5时，f(n!) = 0;
当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）
下面对这个结论进行证明：
(1) 当n < 5时, 结论显然成立。
(2) 当n >= 5时，令n！= （5k * 5(k-1) * ... * 10 * 5） * a，其中 n = 5k + r (0 <= r <= 4)，a是一个不含因子“5”的整数。
对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 <= i <= k)，都含有因子“5”，并且在区间 [5(i-1), 5i] (1 <= i <= k)内存在偶数，也就是说，a中存在一个因子“2”与5i相对应。即，这里的k个因子“5”与 n！末尾的k个“0”一一对应。
n！= （5k * 5(k-1) * ... * 10 * 5） * a = (5k * k!) *a
令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数，则利用上面的的结论有：
f(n!) = g(n!) = g(5k * k!* a) =g(5k * k!)= k + g(k!) = k + f(k!)
所以，最终的计算公式为：
当0 < n < 5时，f(n!) = 0;
当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。
public int method02(int n){
int ret = 0;
if(n<5){
return ret;
}
int k = n/5;
return k + method02(k);
}
时间复杂度为：log5N
解题思路三：
乘积末尾的0的个数依赖于因子中的2的个数和5的个数。对于阶乘来说，每2个数字就至少有一个2的因子，所以2的因子是足够的。5的因子相对少些，至少连续5个数才能保证一定出现一个。注意，这里连续5个书保证出现一个5的因子是指最少的情况。比如1，2，3，4，5，这就只会出现一个。但是考虑 21，22，23，24，25，25 = 5 * 5,所以如果乘以25那就能得到2个5的因子。依次会有3个5的因子…
所以n!中5的个数的计算是：[n/5]+[n/(5*5)]+[n/(5*5*5)]+....
public int method03(int n){
int ret = 0;
int baseNum = 5;
while (n >= baseNum)
{
ret += n/baseNum;
baseNum *= 5;
}
return ret;
}
时间复杂度为：log5N
对于解法二和解法三，我这里写的时间复杂度都为log5N ,但实际验证，解法三比解法二更高效，所以不知道是否时间复杂度写的有问题？高人求解！！！
后记（顿悟）：
算法三之所以优于算法二，因为算法二是用到递归算法，递归一系列的函数调用，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。所以算法三在时间复杂度和空间复杂度上是优于算法二的。
2013.6.20
参考资料：
http://blog.csdn.net/chn_cf/article/details/6541281
http://www.chinaunix.net/old_jh/23/926848.html
http://www.pureweber.com/article/recursive-power-4/
《编程之美》