MDGSF Software Engineer

[算法学习][Math] n的阶乘的末尾有几个零?

2018-04-18
Art

问题:

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, ....

分析:

  1. 如果直接计算出 n! 的大小,那么很快就会溢出。

  2. 如果每一步计算之后,把末尾的零去掉,再做计算,也会很快溢出,因为这个数字也许末尾本来就没有几个零。

  3. 思考末尾的零是怎么来的?

  4. 末尾的零其实是由 5 * 2 = 10 来的。那么零的个数就是由 5 的个数和 2 的个数决定的。

  5. 因为 2 的个数一定比 5 的个数多,所以零的个数就是由 5 的个数决定的。

  6. 那么只需要计算出 n! 中每个数的因子中 5 的个数,就是零的个数。

  7. 那么还可以优化吗?

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 个。


weixingongzhonghao

Comments

Content