问题:
n的阶乘的末尾有几个零?
n = 1, result = 1, 末尾没有一个零
n = 2, result = 2 * 1 = 2, 末尾没有一个零
n = 3, result = 3 * 2 * 1 = 6, 末尾没有一个零
n = 4, result = 4 * 3 * 2 * 1 = 24, 末尾没有一个零
n = 5, result = 5 * 4 * 3 * 2 * 1 = 120, 末尾有 1 个零
n = 6, ....
分析:
-
如果直接计算出 n! 的大小,那么很快就会溢出。
-
如果每一步计算之后,把末尾的零去掉,再做计算,也会很快溢出,因为这个数字也许末尾本来就没有几个零。
-
思考末尾的零是怎么来的?
-
末尾的零其实是由 5 * 2 = 10 来的。那么零的个数就是由 5 的个数和 2 的个数决定的。
-
因为 2 的个数一定比 5 的个数多,所以零的个数就是由 5 的个数决定的。
-
那么只需要计算出 n! 中每个数的因子中 5 的个数,就是零的个数。
-
那么还可以优化吗?
5 10 15 20 25 30 35 40 …. 125 … 625 …
5^1 ….. 5^2 …………. 5^3 … 5^4 …
在 5^1 -> 5^2 这个区间内,5 的个数都是 1 个。 在 5^2 -> 5^3 这个区间内,5 的个数都是 2 个。 在 5^3 -> 5^4 这个区间内,5 的个数都是 3 个。