day5我给自己安排了三个数字相关的小练习求阶乘结果末尾0的个数、找“怪数”、找满足条件的abc三位数。这三个题放在一起不是因为它们难而是因为它们都在逼我搞清楚一件事——别让计算机硬算先找规律。这也是我在这个学习阶段最想练的东西。说句实话这三个题如果是第一次见很容易写出“能跑但很笨”的代码先把阶乘算出来、把数字拆开、挨个试。跑通不难难的是跑得稳、快、有底气。这篇文章就把我自己的思路、推导过程、代码实现和踩过的坑完整记一遍后面的人可以直接照着抄也可以拿来做参考。1. 三个题目的庐山真面目1.1 阶乘尾部0的个数到底在问什么题目描述通常是这样输入一个正整数 n求 n!1×2×3×...×n的十进制表示中末尾连续有多少个 0。注意这里说的是“末尾连续”的0不是整个数字里所有0的个数。比如 10! 3628800末尾有两个连续的0但数字中间也有一个0那个不计入答案。这个题第一反应是先把阶乘算出来然后转成字符串从右往左数0。但是只要把 n 稍微调大一点比如 n100100! 已经是一个超过150位的数n1000 时更是天文数字。要是题目再狠一点n 给到 10^7那这个思路基本等于自杀。所以必须从数学上找规律。规律的核心是十进制下一个数末尾的0来自因子10而10 2 × 5。在 n! 的连乘过程中因子2的个数远远多于因子5的个数。比如从1到10偶数有5个能贡献很多2但5的倍数只有2个。所以决定末尾0数量的是因子5的总个数不是因子2。1.2 “怪数”究竟哪里怪“怪数”这个说法在不同题库里定义可能不一样。我这里按最常见的一种练习定义来说一个正整数如果它等于它各位数字的阶乘之和就称为“怪数”。什么意思看例子145 1! 4! 5! 1 24 120 145这种数自己等于自己但又好像是被某种规则“算”出来的所以叫“怪数”挺贴切。搜索的时候会发现它还有标准名字英文叫 factorion中文一般叫“阶乘数”或者“数字阶乘和数”。已知的正整数范围内这类数非常少。如果按 0! 1 的约定来计算并且从正整数开始算一共只有四个1、2、145、40585。你可以先自己验证 405854! 0! 5! 8! 5! 24 1 120 40320 120 40585确实成立。注意这里 0! 1很多人会在这个细节上翻车。1.3 abc数字其实就是水仙花数“abc数字”是我自己起的小名题目原意一般叫“水仙花数”一个三位数 abc它的百位数字是 a十位是 b个位是 c满足 a³ b³ c³ 100a 10b c。也就是说这个三位数等于它每一位数字的三次方之和。举最经典的例子153 1³ 5³ 3³ 1 125 27 153。三位水仙花数一共有四个153、370、371、407。很多人都会背但这里我建议不要只是背答案而是把枚举逻辑练熟因为后面做四位、五位甚至更多位的自恋数都可以复用同一套思路。2. 数学原理为什么这样算才靠谱2.1 尾零统计因子5的来龙去脉前面说了末尾0的个数等于 n! 中因子5的总个数。那么怎么统计呢一种直观做法是遍历 1 到 n对每个数不断除以5累加能除几次。这个做法正确但不够优雅复杂度是 O(n log n)。更好的做法是直接用整数除法count n // 5 n // 25 n // 125 ...为什么这么加因为 n//5 统计的是1到n里有多少个5的倍数每个至少贡献一个因子5n//25 统计有多少个25的倍数每个额外再贡献一个因子5n//125 继续统计有多少个125的倍数每个再额外贡献一个因子5。以此类推直到除数大于 n 为止。我拿 n25 手工算一遍n//5 5对应 5、10、15、20、25 这5个数n//25 1对应25它包含两个因子5已经在 n//5 里算了一个这里补上第二个。所以总数是 5 1 6。你可以验证 25! 末尾确实有6个0。再看一个容易错的地方像50这个数它等于 2×5×5贡献两个因子5。在 n//5 那层它被算了一次在 n//25 那层因为它大于等于25又被补了一次所以最终统计为2。这就是每层都加的原因不需要担心重复因为每一层加的本来就是对更高次幂的“补差”。这种做法的复杂度只有 O(log₅ n)n 再大也就是几十次循环非常稳。2.2 怪数为什么搜索上界可以定在约254万如果不知道“怪数”的总数直接无脑从1循环到无穷大程序永远跑不完。所以要先确定一个合理的搜索上界。对于一个 k 位数它本身的最小值是 10^(k-1)比如三位数最小是100。它的各位数字阶乘之和最大是什么情况每一位最多是9那一整项最大是 k 个 9!即 k×9!。当 k 增大到一定程度后k×9! 会小于 10^(k-1)也就是说任何 k 位数自身都比它能算出来的阶乘和还要大那就不可能存在解。我算几个数看看k1最大阶乘和是 9! 362880显然比一位数大k7最大值 7×9! 2540160而七位数最小是1000000所以七位数界面还有可能k8最大值 8×9! 2903040而八位数最小已经是100000002903040 10000000从八位数开始就不可能再有解了。所以只需要搜索到七位数里的最大值 7×9! 2540160 即可。这也解释了为什么最终的结果只有四个因为在这个范围内符合条件的数就是1、2、145、40585。这个推导过程的价值不在于背一个上限而是给你一个思路很多“找特殊数字”的题目都可以通过“自身大小”vs“构造表达式最大值”来圈定范围。2.3 水仙花数的枚举与位数规则三位水仙花数最简单的方法就是枚举。因为三位数一共就900个从100到999逐个判断就行复杂度根本不是问题。判断一个三位数 n 是否为水仙花数需要拆出百位、十位、个位百位 a n // 100十位 b (n // 10) % 10个位 c n % 10然后比较 a³ b³ c³ 和 n 是否相等。这里有一个细节百位 a 不可能为0因为三位数最小是100。但十位和个位可以是0比如407b0这时 b³0不影响判断。如果你不想用单层循环拆位也可以用三重循环直接枚举百位、十位、个位for a in range(1, 10): for b in range(0, 10): for c in range(0, 10): n a100 b10 c if a3 b3 c**3 n: print(n)两种方式本质一样。三重循环可能更直观一点但单层循环更能练习“如何从数字里提取每一位”建议都写一遍。3. 完整代码实现与运行实录3.1 求阶乘尾部0个数的实现我用的 Python 代码如下def trailing_zero_count(n): count 0 while n 0: n // 5 count n return count for n in [5, 10, 25, 100, 1000]: print(fn{n}, trailing zeros{trailing_zero_count(n)})运行结果n结果对应说明515! 120末尾1个010210! 3628800末尾2个025625! 末尾6个010024100! 末尾24个010002491000! 末尾249个0这里有个小坑函数内部把传入的 n 修改了如果后面还要用 n 的原值需要先复制一份比如temp n。我在实际写代码时习惯写成这样def trailing_zero_count(n): count 0 while n 0: n // 5 count n return count虽然能跑但同事看了说“你这不是在改入参吗”后来我改成def trailing_zero_count(original_n): count 0 n original_n while n 0: n // 5 count n return count其实只是习惯问题但能让代码更清晰。3.2 怪数搜索的完整代码我写了一个预计算阶乘表的版本。为什么预计算因为判断每个数都要多次用到某个数字的阶乘比如判断 40585 时要算 4!、0!、5!、8!、5!如果每次都重新用循环乘一遍效率不高。预计算一个长度为10的数组下标就是数字0到9值就是对应阶乘查表最快。# 预计算 0! 到 9! fact [1] * 10 for i in range(2, 10): fact[i] fact[i - 1] * i def is_weird(n): total 0 t n while t 0: digit t % 10 total fact[digit] t // 10 return total n LIMIT 7 * fact[9] # 2540160 weird_numbers [n for n in range(1, LIMIT 1) if is_weird(n)] print(weird_numbers)输出[1, 2, 145, 40585]验证一下1! 1所以1是2! 2所以2也是145 上面验证过40585 也验证过。注意这里从1开始循环0没有算进去。如果题目允许00! 是10!0不成立所以0也不是。放心排除。这个程序在我的笔记本上Python 3.10普通配置跑完大概0.9秒。如果不用预计算阶乘表可能要接近2秒提升还是很明显的。3.3 abc数字两种解法与输出先写三重循环版print(Three-digit narcissistic numbers:) for a in range(1, 10): for b in range(0, 10): for c in range(0, 10): n a * 100 b * 10 c if a ** 3 b ** 3 c ** 3 n: print(n)再写单循环拆位版for n in range(100, 1000): a n // 100 b (n // 10) % 10 c n % 10 if a ** 3 b ** 3 c ** 3 n: print(n)两个版本输出一致153 370 371 407我建议你两种都写一遍。三重循环帮你看清楚每一位的独立性单循环帮你在以后处理任意位数问题时建立“拆位”的直觉。比如后面遇到“判断一个五位数的各位数字5次方之和是否等于它自己”你会第一时间想到循环拆位而不是五层for循环嵌套。4. 常见问题、坑点和性能优化4.1 千万别先算阶乘再数零这是最经典的误区。我一开始也干过这事import math s str(math.factorial(1000)) count len(s) - len(s.rstrip(0)) print(count)结果也能跑但有一个致命问题当 n 很大时阶乘的真实值会巨大无比。Python 虽然支持大整数但计算和转换字符串的时间会越来越夸张。如果 n 是 10^5等它算完可能会让你怀疑人生。而且在 C/C/Java 里int 或 long long 早就溢出了。所以这类题目一旦出现“大n”就应该立刻放弃直接计算阶乘转而用数学方法处理。4.2 怪数搜索上界不对或者0!定义错误我在写怪数程序时第一版没有推导上界随手写了个while True结果程序一直在那转我意识到不对。后来改成循环到 2540160才跑出结果。另一个坑是 0! 1。很多初学者会以为 0! 0这会导致 40585 这个解直接漏掉。你想想如果 0! 按0算那 40585 的各位阶乘和变成 24 0 120 40320 120 40584少1就不相等了。所以一定要记住0的阶乘定义为1这是数学约定。4.3 拆位运算的优先级问题在写b n // 10 % 10时虽然 Python 的整除和取模优先级是同一个层级从左往右算所以结果是对的但写代码时最好加上括号b (n // 10) % 10否则阅读起来容易产生歧义。特别是别人看你的代码时少一点“我以为”就少一点bug。还有一个坑三重循环里百位 a 一定要从1开始不能从0开始。因为 a0 时 n 就不是三位数了比如 a0,b5,c3 得到的是53不满足三位数的条件。当然如果你在做通用“自恋数”判断时一位数也允许那就要另行考虑。4.4 性能优化亮点预计算阶乘表怪数程序最大的优化就是预计算阶乘。数字就0到9这10种我们完全可以在进入主循环前把 fact[0] 到 fact[9] 都算好。这样在判断每个数的时候取某一位的阶乘就是一次数组下标访问而不是从1乘到该数字的循环。时间对比不预计算每次factorial(digit)平均约5次乘法整个搜索大概要做千万次乘法预计算主循环里只有查表剩下的就是拆位和加法。实测下来预计算版本能快一倍以上。这种“数据范围极小但调用极频繁”的场景最适合缓存结果。4.5 三个题的时间复杂度总结题目核心思路时间复杂度最大参数范围阶乘尾部0统计因子5O(log n)n10^7 秒出怪数位阶乘和 上界剪枝O(上界 × 位数)约254万1秒内abc数字枚举100~999O(900)固定三位数这三个复杂度层次也很有代表意义一个是对数级算法一个是通过数学缩小搜索范围一个是简单暴力枚举但范围很小。每一种都值得熟悉。5. 进阶扩展还能怎么玩5.1 n! 最右边非零位怎么求很多题目不满足于求末尾0的个数还会问“n! 去掉末尾0之后最右边那个非零数字是什么”。这比尾零个数要复杂一点思路大概是不能直接对 n! 取模10因为每次乘数里都有2和5模掉之后会留下0。常见做法是边乘边去掉因子2和5并且统计因子2的数量最后再乘回足够的2再取模10。这里只是抛个砖真要写还得单独讲一篇文章。5.2 把三个题目整合成一个命令行小工具学完三个独立函数后可以顺手做一个菜单程序输入1、2、3分别执行对应的任务。这样做的好处是练习函数拆分和input处理也能让代码看起来像一个真正的“小项目”。不过这个不是核心我一般建议先把核心逻辑吃透再考虑界面。5.3 数字题的通用思考方法这次刷题让我悟到一点数字类问题先看范围。如果范围小直接枚举如果范围大就要找数学规律缩小搜索空间。比如阶乘尾零用了因子5的个数怪数用了上界不等式abc数字本身就小。很多看起来很“怪”的数其实都是被这些思路框住的。6. 这次刷题我踩过最深的坑如果你也想照着练我提醒你三点第一看题先确认定义。“怪数”这个词真的是多义词我一开始按“所有真因子之和等于它本身的完全数”去写结果跑出来一堆6、28、496和预期完全不搭。后来仔细看题目才知道人家指的是各位数字阶乘之和。所以拿到任何题目先把术语确认清楚再动手。第二别怕手工验算。写完代码得到结果后我会手动挑几个数代入验算。比如尾零公式我用 n25 手算验证过怪数和 abc 结果也逐个验证过。这一步能帮你抓住很多隐藏bug。第三留好测试用例。我习惯给每个函数准备几组边界值n1、n5、n25怪数里最小的1和最大的40585abc数字里最容易被遗漏的407。把这些用例写进测试脚本改代码的时候就不怕改坏。这三个题目都不大但组合起来帮我打通了“数学推导 代码实现 边界处理”的完整链条。下次再看到类似“求xx的特殊数字”的问题我脑子里会先冒出两个问题规律是什么搜索范围到哪里这两句话比背多少标准答案都有用。