经典面试题：100的阶乘有几个结尾零

大家好，欢迎来到IT知识分享网。

100! = 100*99*98*97*…*2*1

先看看结尾零是如何形成的：结尾零当一个5的倍数与2的倍数相乘时就会形成。所以我们只要计算有几对(2,5)，就能知道有几个结尾零。

先来数5因子有几个：在100内，5作为因子的数有5, 10, 15, 20, 25… 总共有20个。但是注意到25, 50, 75, 100都包含了2个5作为因子(25=5*5, 50=2*5*5)

因此对于这些数，我们要多数一次。所以总共就是有24个5因子。

从公式角度： 5因子的数目 = 100/5 + 100/(5^2) + 100/(5^3) + … = 24 （必须是整数）

现在再来数2因子有几个：2, 4, 6, 8, 10, … 总共有100/2=50个2因子，100/4=25个4因子（要多计数一次），100/8=12个8因子（要多计数一次）,…

所以  

                         2因子的数目 = 100/2 + 100/(2^2) + 100/(2^3) + 100/(2^4) + 100/(2^5) + 100/(2^6) + 100/(2^7) + … = 97

综上所述，共有24个5因子 和 97个2因子，所以能凑24 个 (2,5) 对。

因此100的阶乘也就有24个结尾零

知道思路和公式后，写程序应该很容易。什么时候有空时补上程序

Update: 11.16

现在补上程序，分别在两个OJ上测过了，都没问题。

POJ http://poj.org/problem?id=1401

import java.io.*; import java.util.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); int cnt = cin.nextInt(); int input; for(int i=0; i<cnt; i++){ input = cin.nextInt(); System.out.println(trailingZeros(input)); } } // 只用计算5因子的个数即可，因为5因子的个数肯定小于2因子的个数 public static int trailingZeros(int input){ int quotient; int fiveFactors = 0; quotient = input / 5; int i = 1; while(quotient != 0){ fiveFactors += quotient; i++; quotient = (int)(input / Math.pow(5, i)); } return fiveFactors; } }

安徽大学的OJ  http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=402

package Factorial; import java.io.*; import java.util.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); int input = cin.nextInt();; while(input != 0){ System.out.println(trailingZeros(input)); input = cin.nextInt();; } System.out.println(); } // 只用计算5因子的个数即可，因为5因子的个数肯定小于2因子的个数 public static int trailingZeros(int input){ int quotient; int fiveFactors = 0; quotient = input / 5; int i = 1; while(quotient != 0){ fiveFactors += quotient; i++; quotient = (int)(input / Math.pow(5, i)); } return fiveFactors; } }

PS：用Java做这类OJ怎么样都感觉是非主流，没办法为了面试还是用Java吧。

Ref:

http://www.mytechinterviews.com/how-many-trailing-zeros-in-100-factorial