输入一个正整数n,求n!(即阶乘)末尾有多少个0? 比如: n = 10; n! = 3628800,所以答案为2
输入为一行,n(1 ≤ n ≤ 1000)
输出一个整数,即题目所求
10
2
先求出n阶乘的数
拆分成char数组
倒着遍历判断是不是0
最简单的思路就是把所有的数字进行分解质因数,例如:
6 = 2 * 3
15 = 3 * 5
100 = 2^2 * 5^2
576 = 2^6 * 3^2
那么我们在计算n的阶乘时,实际上就是把所有小于等于n的正整数分解成质因数,然后再将其乘到一起,那么末尾0的个数实际上就是2*5的个数,而2的个数明显是很多很多的,所以问题就转化成了5的个数。
而只有5的倍数才有5这个因数,所以,问题就进一步简化为小于等于n的数中有多少个数是5的倍数
能被5(5^1)整除的提供1个0
能被25(5^2)整除的提供2个0
能被125(5^3)整除的提供3个0
能被625(5^4)整除的提供4个0
所以 结果= n/5 + n/25 + n/125 + n/625
package answer20200331; import java.math.BigDecimal; public class Test { public static void main(String[] args) { int i = 200; solve1(i); solve2(i); } /** * 解决思路1 * * @param i */ public static void solve1(int i) { BigDecimal result = new BigDecimal("1"); for (int j = 1; j <= i; j++) { result = result.multiply(new BigDecimal(j + "")); } System.out.println(i + "的阶乘为" + result); String reString = result.toString(); char[] charArray = reString.toCharArray(); int zeroNum = 0; for (int j = charArray.length - 1; j >= 0; j--) { if ((charArray[j] == "0".charAt(0))) { ++zeroNum; } else { break; } } System.out.println("解决思路1 最后0的数量" + zeroNum); } /** * 解决思路2 * * @param i */ public static void solve2(int i) { int zeroNum = 0; for (int j = 1; j <= i; j++) { int temp = j; while (temp % 5 == 0) { // 证明5能除尽,递归判断能被几个5除尽 temp = temp / 5; // 每次能被除尽加一个0 ++zeroNum; } } System.out.println("解决思路2 最后0的数量" + zeroNum); } }