Python中计算阶乘末尾零的精确方法与常见误区解析

def zeros_legendre(n: int) -> int:
    """
    使用勒让德公式计算N!的末尾零数量。

    参数:
        n (int): 要计算阶乘的数字。

    返回:
        int: N!的末尾零数量。
    """
    if n < 0:
        raise ValueError("阶乘只对非负整数定义")
    if n == 0:
        return 0  # 0! = 1, 没有末尾零

    count = 0
    i = 5
    while i <= n:
        count += n // i
        # 防止溢出，检查 i * 5 是否仍然小于或等于 n
        # 否则 i = i * 5 可能会导致 i 变得非常大
        # 更好的做法是检查 i <= n // 5
        if i > n // 5: # 避免 i * 5 溢出，或者当 i 已经很大时，直接退出
             break
        i *= 5 
    return count

# 示例
print(f"zeros(6) = {zeros_legendre(6)}")    # 输出: zeros(6) = 1
print(f"zeros(12) = {zeros_legendre(12)}")  # 输出: zeros(12) = 2
print(f"zeros(20) = {zeros_legendre(20)}")  # 输出: zeros(20) = 4
print(f"zeros(100) = {zeros_legendre(100)}") # 输出: zeros(100) = 24

# 错误示例：计算整个阶乘并尝试字符串处理
def factorial(x):
  if x == 0: # 修正：0! = 1
    return 1
  if x == 1:
    return x 
  else:
    return x * factorial(x - 1)

def zeros_incorrect(n):
  if n < 0:
      raise ValueError("阶乘只对非负整数定义")
  if n == 0:
      return 0

  fact_str = str(factorial(n)) # 巨大的数字可能导致问题

  # 错误的逻辑：试图移除非零数字
  # list1 = list(fact_str)
  # list2 = list1[:]
  # for num_char in list1:  
  #   if num_char != '0': # 修正：应与字符串'0'比较
  #     list2.remove(num_char)
  #   else:
  #     # 这里的逻辑非常复杂且不正确，试图处理零和非零的混合
  #     pass

  # 正确的字符串处理方式是计数末尾零
  count = 0
  for char in reversed(fact_str): # 从末尾开始反向遍历
      if char == '0':
          count += 1
      else:
          break # 遇到非零数字即停止
  return count

# print(zeros_incorrect(20)) # 对于N=20，仍能工作，但效率低且不推荐
# 对于更大的N，如zeros_incorrect(100)，factorial(100)会生成一个非常长的字符串
# 尽管Python的整数可以处理任意大小，但将其转换为字符串并遍历仍然是低效的。

def count_trailing_zeros_str_enumerate(num_val: int) -> int:
    """
    将数字转换为字符串并反转，然后使用 enumerate 计数末尾零。

    参数:
        num_val (int): 任意一个整数。

    返回:
        int: 数字末尾零的数量。
    """
    if num_val == 0:
        return 1 # 特殊情况：数字0本身算作一个零

    num_str_reversed = str(num_val)[::-1] # 反转字符串

    for i, char in enumerate(num_str_reversed):
        if char != "0":
            return i # 遇到第一个非零字符，返回其索引，即之前零的数量

    # 如果所有字符都是'0' (例如 "000")，则返回字符串长度
    return len(num_str_reversed)

# 示例
print(f"count_trailing_zeros_str_enumerate(720) = {count_trailing_zeros_str_enumerate(720)}") # 输出: 1
print(f"count_trailing_zeros_str_enumerate(479001600) = {count_trailing_zeros_str_enumerate(479001600)}") # 输出: 2
print(f"count_trailing_zeros_str_enumerate(1000) = {count_trailing_zeros_str_enumerate(1000)}") # 输出: 3
print(f"count_trailing_zeros_str_enumerate(0) = {count_trailing_zeros_str_enumerate(0)}") # 输出: 1 (特殊处理)

def count_trailing_zeros_str_loop(num_val: int) -> int:
    """
    将数字转换为字符串并反转，然后使用显式循环计数末尾零。

    参数:
        num_val (int): 任意一个整数。

    返回:
        int: 数字末尾零的数量。
    """
    if num_val == 0:
        return 1 # 特殊情况：数字0本身算作一个零

    num_str_reversed = str(num_val)[::-1]
    count = 0
    for char in num_str_reversed:
        if char == "0":
            count += 1
        else:
            break # 遇到非零字符即停止
    return count

# 示例
print(f"count_trailing_zeros_str_loop(720) = {count_trailing_zeros_str_loop(720)}") # 输出: 1
print(f"count_trailing_zeros_str_loop(479001600) = {count_trailing_zeros_str_loop(479001600)}") # 输出: 2
print(f"count_trailing_zeros_str_loop(1000) = {count_trailing_zeros_str_loop(1000)}") # 输出: 3
print(f"count_trailing_zeros_str_loop(0) = {count_trailing_zeros_str_loop(0)}") # 输出: 1 (特殊处理)