Python算法例31 阶乘尾部零的个数

2023-12-31 05:40:54

1. 问题描述

计算n的阶乘中尾部零的个数。

2. 问题示例

输入11,输出2,11!=39916800,结尾有2个0;输入5,输出1,5!=120,结尾有1个0。

3. 代码实现

def trailing_zeros(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

# 测试样例
print(trailing_zeros(11))  # 输出2
print(trailing_zeros(5))   # 输出1

该算法的思路是,一个零的出现是由于2和5相乘得到的,而阶乘中2的数量远大于5的数量。因此,我们只需要计算阶乘中包含多少个5即可。

在循环中,我们将n除以5,并将结果加到计数器count上。然后,将n除以5继续进行循环操作,直到n小于5为止。最后,返回count的值即为尾部零的个数。

这种算法的时间复杂度为O(\log n),其中n为输入的数字。

要计算尾部零的个数,我们可以观察到,尾部零的个数取决于阶乘中因子5的个数。因为每个因子5都能与一个偶数相乘得到10,进而贡献一个尾部零。

更优的算法是利用数学的方法来计算因子5的个数,而不需要遍历每个数字。

def trailing_zeros(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

# 测试样例
print(trailing_zeros(11))  # 输出2
print(trailing_zeros(12))   # 输出2

这个算法的时间复杂度仍然是O(\log n),但是它比遍历每个数字的方法要快得多。它通过将n除以5来计算因子5的个数,并将结果累加到计数器count上。然后,将n除以5继续进行循环操作,直到n小于5为止。最后,返回count的值即为尾部零的个数。

这种算法利用了因子5的特性,能够更高效地计算尾部零的个数。

文章来源:https://blog.csdn.net/m0_62110645/article/details/135311381
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。