题目描述
题目:阶乘后的零
给定一个非负整数 n
,计算 n!
(n
的阶乘)末尾有多少个零。阶乘 n!
是所有小于及等于 n
的正整数的乘积。
阶乘末尾的零是由因子 2
和 5
相乘产生的(因为 10 = 2 * 5
),而在阶乘的质因数分解中,2
的因子通常比 5
的因子多,所以计算末尾零的个数主要取决于 5
的因子的个数。
示例
输入:
n = 5
输出:
1
解释:5! = 120
,末尾有 1 个零。输入:
n = 10
输出:
2
解释:10! = 3628800
,末尾有 2 个零。
PHP 代码示例
function trailingZeroes($n) {
$count = 0;
while ($n >= 5) {
$n /= 5;
$count += (int)$n;
}
return $count;
}
// 测试
echo trailingZeroes(5); // 输出 1
echo "\n";
echo trailingZeroes(10); // 输出 2
Python 代码示例
def trailing_zeroes(n):
count = 0
while n >= 5:
n //= 5
count += n
return count
# 测试
print(trailing_zeroes(5)) # 输出 1
print(trailing_zeroes(10)) # 输出 2
JavaScript 代码示例
function trailingZeroes(n) {
let count = 0;
while (n >= 5) {
n = Math.floor(n / 5);
count += n;
}
return count;
}
// 测试
console.log(trailingZeroes(5)); // 输出 1
console.log(trailingZeroes(10)); // 输出 2
逻辑说明
在以上代码中,我们通过不断将 n
除以 5
并累加商(向下取整),直到 n
小于 5
为止。这是因为 n!
中每 5
个连续整数就会贡献一个 5
的因子到质因数分解中(而每 25
个会贡献两个,每 125
个会贡献三个,以此类推),而 2
的因子总是足够的。因此,我们只需要计算 5
的因子的个数即可确定阶乘末尾零的个数。