自幂数这个话题乍一看像是数学课本里那种“了解一下就行”的小知识点但我实际拿它做过一轮完整的算法练习和教学演示之后发现它特别适合用来打通“数学定义到代码实现”之间的那道墙。所谓自幂数简单说就是一个n位数它的每一位数字的n次方之和恰好等于它本身。最出名的例子是153三位数1³5³3³112527153完美闭环。这类数在圈子里常被叫做水仙花数、阿姆斯特朗数叫法不同但指向同一个东西。我写这篇东西是想把“02自幂数”这个练习项目从头到尾拆一遍——它适合刚学编程想找练手题的人也适合需要给新人讲算法思路的带教者更适合那些想弄明白“为什么暴力枚举能跑、什么时候该剪枝”的实践者。下面全部是我自己动手跑过、改过、踩过坑之后整理出来的内容不玩虚的。1. 项目整体设计与思路拆解1.1 为什么选自幂数作为算法练习载体我挑自幂数来做练习项目核心原因是它的定义足够干净但实现路径却有好几条能自然拉开难度梯度。定义里只有两个动作拆位、求幂、求和、比较。可一旦你把位数n放开问题就来了——n位数的范围是从10^(n-1)到10^n-1n稍微大一点枚举量就爆炸。这就逼着你去想能不能不枚举全部能不能利用幂次的单调性做剪枝能不能用查表把幂运算省掉对比一下其他常见的入门题比如素数判断、斐波那契自幂数的好处是它同时涉及数位操作和幂运算两个基础技能点而且结果集很小、验证起来特别直观。你跑完程序把结果往数学定义里一代对不上就是错没有模糊地带。这种“即时可验证性”对新手特别友好调试的时候心里有底。另一个我比较看重的点是自幂数天然适合做分位数讨论。一位数、两位数、三位数……每个位数区间的解的数量和分布都不一样你可以按位数分段跑观察程序在不同规模下的表现。这种“同一问题、不同规模”的对照比单纯刷一道题收获大得多。1.2 暴力枚举与剪枝优化的取舍逻辑最直接的实现就是暴力枚举对每个n位数拆位、求n次方、求和、比较。这个方案的优势是逻辑零歧义写出来基本不会错适合作为第一版基线。但它的代价也很明显——n7的时候要检查900万个七位数每个数拆7位、做7次幂运算粗算就是几千万次乘法纯Python跑起来肉眼可见地慢。那要不要一上来就上剪枝我的经验是不要。先写暴力版跑出正确结果把它当作“标准答案生成器”后面所有优化版本都拿它来对拍。这个顺序很重要我见过不少人直接写优化版结果剪枝条件写错跑出来的结果少了几个数自己还不知道因为没有基线可比。剪枝的核心思路是利用幂次和的上下界。比如你在枚举过程中已经确定了前k位剩下的位还没定那当前幂次和加上“剩余位全取9”的最大可能值如果还小于当前枚举区间的下界就可以直接砍掉这一支。反过来如果当前幂次和已经超过上界也可以提前退出。这个思路本质上是深度优先搜索加界限剪枝把“逐个数检查”变成“逐位构造”。我实测下来n≤7的时候暴力枚举还能接受n8开始就必须上剪枝了否则时间成本不成比例。这个分界线不是绝对的跟语言、机器都有关系但大致在这个量级。1.3 幂运算的预处理策略还有一个特别容易被忽略的优化点幂运算查表。自幂数的计算里0到9这十个数字的n次方会被反复用到无数次。与其每次都调pow(d, n)不如一开始就把pow_table[d] d**n算好存成一个长度10的数组后面直接索引。这个改动的收益有多大我做过对比在n7的暴力枚举里查表版本比实时pow版本快了大概三到四成。原因很简单pow函数内部有通用幂运算的逻辑分支而查表就是一次数组访问省掉了函数调用和循环乘方。对于这种“底数只有10种、指数固定”的场景查表是稳赚不赔的买卖。更进一步如果你用C或者Rust这类语言还可以把pow_table做成编译期常量连运行时初始化都省了。Python里虽然做不到编译期但模块加载时算一次存全局也完全够用。2. 核心细节解析与实操要点2.1 数位拆解的几种写法与坑拆位看着简单但写法不同坑也不同。最常见的两种一种是转字符串再逐字符转int另一种是用取模和整除循环剥位。字符串写法代码短可读性好def digits_str(num): return [int(c) for c in str(num)]但它有个隐性成本——类型转换。每个数都要走一遍int转str再转回int的流程在百万级枚举里这个开销不可忽视。而且字符串写法默认你处理的是非负整数负数得额外处理自幂数定义里一般只讨论正整数所以这点还好。取模写法更“底层”def digits_mod(num): result [] while num 0: result.append(num % 10) num // 10 return result这个写法没有类型转换纯算术操作速度快。但要注意两个细节一是得到的位数是逆序的个位在前如果你对顺序有要求得反转二是num0的情况循环一次都不进返回空列表得单独处理。我在第一版里就栽在这——忘了0这个边界结果一位数里的0没被正确识别。提示自幂数讨论通常从1开始0是否算自幂数在不同资料里有分歧0¹0形式上成立。做练习项目时建议在代码注释里明确你的约定避免结果对不上时扯皮。2.2 幂次和的累加与提前终止累加幂次和的时候有一个特别实用的技巧边加边比较超了就停。因为所有幂次都是非负的和只会越加越大。如果你已经知道当前数的上界比如它是个n位数最大就是10^n-1那一旦部分和超过这个上界后面不用算了直接判定不是自幂数。这个提前终止在暴力枚举里能省不少时间尤其是那些高位数字很大的数往往加两三项就超了。实现上就是在循环里加一个判断def is_armstrong(num, n, pow_table): total 0 temp num limit 10 ** n - 1 while temp 0: total pow_table[temp % 10] if total limit: return False temp // 10 return total num注意这里的limit用的是“n位数的最大值”而不是num本身。为什么因为我们要判断的是“和是否等于num”如果和已经超过n位数的最大可能值那它肯定不等于任何n位数提前退出是安全的。用num本身做上界也行但那样判断更频繁、收益略小用limit更宽松一点减少误杀。2.3 位数n的确定与边界处理自幂数的定义依赖位数n所以第一步永远是确定n。对于给定的数numn len(str(num))或者用循环数位数。这里有个容易翻车的地方前导零。比如数字10它是两位数但如果你的拆位逻辑把前导零也算进去就可能把位数搞错。自幂数定义里不认前导零所以位数就是有效数字的个数。另一个边界是一位数。一位数n1每位数字的1次方就是它自己所以1到9全都满足定义0¹0也满足看约定。这意味着如果你从1开始枚举一位数结果会是1、2、3、4、5、6、7、8、9全中。很多人第一次跑程序看到这个结果会愣一下以为程序写错了其实是定义使然。我在带新人的时候专门强调过这一点一位数全是自幂数这不是bug是数学事实。2.4 结果去重与排序的细节如果你是按位数分段跑最后合并结果时要注意去重。正常情况下不同位数的自幂数不会重复位数不同数值范围就不重叠但如果你在代码里对n的处理有误比如把同一个数用不同的n算了两遍就可能出现重复。稳妥的做法是最后统一放进一个set再排序输出。排序本身没什么技术含量但输出格式值得讲究。我习惯按位数分组打印每组一行这样一眼能看出每个位数区间有几个解。对于教学演示来说这种分组展示比一坨数字堆在一起清楚得多。3. 实操过程与核心环节实现3.1 第一版纯暴力基线实现先上完整的第一版代码目标只有一个——正确不管快慢。def find_armstrong_bruteforce(max_n): results {} for n in range(1, max_n 1): low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found [] for num in range(low, high 1): total 0 temp num while temp 0: d temp % 10 total d ** n temp // 10 if total num: found.append(num) results[n] found return results这段代码我建议你亲手敲一遍别复制。敲的过程中你会自然去想几个问题low为什么n1时特殊处理因为10^01但一位数从1开始0要不要算看你约定。high为什么是10^n-1因为n位数的最大值就是全9。这些细节自己推一遍比看别人写十遍都管用。跑n1到6结果应该是一位数9个1-9三位数4个153、370、371、407四位数3个1634、8208、9474五位数3个54748、92727、93084六位数1个548834。两位数没有七位数有4个1741725、4210818、9800817、9926315。这些结果你拿计算器随手验一个比如94749⁴4⁴7⁴4⁴656125624012569474对得上。3.2 第二版查表加提前终止在第一版基础上做两个改动幂表预计算、部分和超限提前退出。def find_armstrong_optimized(max_n): results {} for n in range(1, max_n 1): pow_table [d ** n for d in range(10)] low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found [] for num in range(low, high 1): total 0 temp num while temp 0: total pow_table[temp % 10] if total high: break temp // 10 else: if total num: found.append(num) results[n] found return results这里用了Python的for-else结构while正常走完没被break才进else。这个写法比较紧凑但如果你不熟悉for-else改成标志位也行可读性优先。实测n6的时候优化版比暴力版快大约一半n7的时候差距拉大到三倍左右。这个提升主要来自提前终止——七位数里大量数的幂次和在前几位就超了省掉了后面的计算。3.3 第三版按位构造的剪枝搜索到了n8以上逐个数枚举开始吃力这时候换思路不枚举数枚举数字组合。因为自幂数的幂次和只跟“每个数字出现几次”有关跟数字的排列顺序无关。比如153和351的幂次和是一样的都是1³5³3³只是数值不同。所以我们可以按“0到9各用几次”来构造总次数等于n。这个思路的搜索空间是“把n个位置分配给10个数字”的组合数比10^n小得多。具体实现用递归每层决定当前数字用几次同时维护当前幂次和与已用位数。剪枝条件当前幂次和加上“剩余位数全取9的幂”还小于目标下界或者当前幂次和已经超过上界就砍掉。def find_armstrong_dfs(n): pow_table [d ** n for d in range(10)] low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found set() def dfs(digit, remaining, current_sum, combo): if remaining 0: if low current_sum high: digits_of_sum sorted(str(current_sum)) if digits_of_sum sorted(combo): found.add(current_sum) return if digit 9: return max_possible current_sum remaining * pow_table[9] if max_possible low: return if current_sum high: return for count in range(remaining, -1, -1): dfs(digit 1, remaining - count, current_sum count * pow_table[digit], combo str(digit) * count) dfs(0, n, 0, ) return sorted(found)这段代码的关键在最后的验证DFS构造出的current_sum要反过去检查它的各位数字组合是否和combo一致。为什么因为DFS是按“假设用了哪些数字”来累加幂次和的但累加出来的和其实际数字组成未必和假设一致。只有一致了才说明这个和确实是由这些数字构成的才是真正的自幂数。这个“构造后回验”是组合搜索类问题的通用套路我第一次写的时候漏了这步结果多出一堆假解。n8用这个版本跑秒出结果。n9、n10也能在可接受时间内完成。再往上就得考虑更精细的剪枝或者换语言了。3.4 参数选择与性能对照把三个版本在不同n下的表现整理成表方便你判断什么时候该用哪版位数n暴力版耗时查表优化版DFS剪枝版解的个数50.1s0.1s0.1s36~0.5s~0.25s0.1s17~5s~1.5s~0.1s48不可接受~15s~0.5s39不可接受不可接受~3s410不可接受不可接受~20s1这些数字是我在一台普通笔记本上跑出来的具体值会因机器而异但量级关系是稳定的。你可以看到n≤6三个版本差别不大n7开始DFS优势明显n≥8基本只能靠DFS。这个表的意义在于帮你建立“规模感”——知道什么规模该上什么手段比死记某个算法重要得多。注意DFS版本里那个combo str(digit) * count的字符串拼接在n很大时会有内存开销。如果追求极致可以改成用计数数组传递但可读性会下降。练习项目里我建议保留字符串版清晰优先。4. 常见问题与排查技巧实录4.1 结果少了几个数怎么查这是最高频的问题。程序跑完结果比预期少第一反应往往是“剪枝剪过头了”。排查顺序我一般是这样的先关掉所有剪枝退回暴力版确认暴力版结果和数学预期一致。如果暴力版也少那问题在基础逻辑不在剪枝。基础逻辑里最常见的错是位数n算错——比如把num100的位数算成2因为拆位循环只走了两次就遇到0退出导致用2次方去算三位数。修法是拆位前先确定n或者用len(str(num))。如果暴力版对、优化版少那就是剪枝条件写错了。重点检查两个不等式方向max_possible low该砍current_sum high该砍方向反了就会误杀。我见过把写成导致边界解被砍的情况153这种刚好卡在边界的数就丢了。4.2 结果多了假解怎么定位结果多出来八成是回验环节缺失或写错。DFS版本里如果忘了检查“current_sum的数字组成是否等于combo”就会把一堆幂次和碰巧落在区间内、但数字组成对不上的数也算进去。定位方法很简单把多出来的数单独拿出来手动算它的幂次和再看这个和的数字组成和原数是否一致。不一致就是回验没做对。还有一种多解的情况是重复计数。比如DFS里对同一个数字组合的不同排列都算了一遍但最后没去重。用set存结果就能解决代价是丢失顺序输出前排个序即可。4.3 大n跑不动时的应急手段n跑到9、10以上如果机器慢或者语言效率低可以上几个应急手段。第一是换语言同样的DFS逻辑用C写n10能压到一两秒。第二是并行化按首位数字或者按数字组合的第一位分片多进程各跑各的最后合并。第三是限制搜索深度如果你只关心“有没有解”而不关心“所有解”找到第一个就可以停。不过我得说句实在话自幂数这个练习项目的价值主要在n≤8这个区间再往上更多是性能调优的炫技数学上的新东西不多。把n1到8跑通、三个版本对拍一致这个项目的核心目标就达成了。4.4 常见问题速查表现象可能原因排查动作一位数结果只有部分0的约定不明确或循环从0开始漏了检查low的取值和0的处理两位数有解位数n算错用了错误的指数打印每个候选的n值核对结果整体偏移幂表索引错位或指数用错抽查一个已知解手动验算优化版比暴力版少剪枝不等式方向反了临时关剪枝对比结果DFS版多出假解回验环节缺失检查combo与current_sum的数字组成比对大n内存暴涨字符串拼接或递归栈过深改用计数数组、增大递归限制5. 从练习到教学的延展用法5.1 用自幂数讲“定义到代码”的翻译我带新人的时候喜欢拿自幂数当第一个“完整翻译”案例。数学定义是“n位数各位n次方和等于自身”翻译成代码就是三层确定n、拆位求幂和、比较。每一层都能单独拎出来讲——确定n讲边界拆位讲循环和取模比较讲浮点陷阱这里没有因为全是整数正好可以对比讲为什么有些题不能用浮点。这个案例的好处是没有外部依赖不用装库、不用配环境打开编辑器就能写。新人写完跑出153那种“我让电脑算出了数学规律”的成就感比刷十道输入输出题都强。5.2 用版本迭代讲“先正确后优化”三个版本的演进路线本身就是一堂工程课。第一版只求对第二版做常数优化第三版换算法范式。每一步的动机都清清楚楚第一版慢是因为重复算幂所以第二版查表第二版还是逐个枚举所以第三版换组合搜索。这种“问题驱动改进”的叙事比直接甩一个最优解更能让人理解优化的来龙去脉。我通常会让学生自己先跑第一版跑到n7卡住再引导他们想“哪里在重复劳动”。大部分人能想到查表少数人能想到剪枝极少数能跳到组合搜索。这个分层正好对应不同的思维水平讨论起来有层次。5.3 延展方向其他进制与变体自幂数的定义可以平移到任意进制。二进制下的自幂数、十六进制下的自幂数都是有意思的变体。实现上只需把“10”换成进制基数“9”换成“基数-1”幂表长度跟着变。这个延展能帮你理解“十进制只是特例”对进制转换的理解也会更深。另一个变体是幂次不固定为位数比如固定用平方或者立方。固定立方的话就是“各位立方和等于自身”的数153那批还在但位数不再限制为3。这类变体的搜索空间和剪枝条件都要重新推适合作为进阶练习。6. 我踩过的几个具体坑第一个坑是0的处理。我第一版代码里一位数从0开始枚举结果0也被算进去了。数学上0¹0确实成立但很多资料不把0列为自幂数。这个分歧本身不是错错在我没在代码里明确约定导致后面跟别人的结果对不上时浪费了半天排查。现在的习惯是代码开头写一行注释明确“本实现从1开始0不计入”一劳永逸。第二个坑是幂表的初始化位置。我一开始把pow_table放在最外层循环外面想着“算一次就够了”结果n变化时表没更新用的还是上一个n的幂值跑出来的结果全乱。这个bug特别隐蔽因为小n的时候可能碰巧对比如n1和n2的某些数字幂值相同到大n才暴露。修法很简单把表放进n的循环里每个n重新算。第三个坑是DFS的递归深度。n10的时候递归深度到10层Python默认递归限制是1000够用。但如果我为了通用性把数字范围从10扩到更大比如考虑多进制深度可能上去就得调sys.setrecursionlimit。这个坑我当时没遇到是后来做变体时踩的提前说一声省得你重复。第四个坑是结果验证的偷懒。有次我图省事只拿前几个结果跟记忆里的对后面的没验结果一个剪枝边界写错中间漏了两个数直到做版本对拍才发现。教训是任何优化版本都必须和暴力基线全量对拍不能抽查。对拍代码就三行写起来不费事省下的排查时间是以小时计的。7. 完整可复现的操作清单如果你想把整个项目从头跑一遍按这个顺序来写暴力版跑n1到6记录结果手动验算至少两个解。写查表优化版和暴力版全量对拍确认结果一致记录耗时对比。写DFS剪枝版同样全量对拍重点检查n7、8的结果。把三个版本的结果整理成表观察解的个数随n的变化规律。尝试n9、10记录DFS版的耗时感受规模增长。选一个变体其他进制或固定幂次改一版验证思路迁移。每一步的产出都留着尤其是对拍记录。这些记录在写总结或者给别人讲的时候比代码本身更有说服力——它证明你不是碰巧跑对而是系统验证过。最后分享一个我常用的验证小技巧拿结果里的任意一个数用计算器或者手算把幂次和重新算一遍和原数比对。这个动作看着笨但能抓出“程序内部自洽但定义理解错”的问题。比如如果你把“各位n次方”错理解成“各位的位数次方再乘位数”程序自己跑得通但结果和数学定义对不上手算一验就露馅。自幂数这个项目数学定义就是最终裁判代码只是翻译翻译得对不对拿原文对一遍最踏实。 
长河君 · 2026/10/31 17:14:07 · 阅读 1.2k 自幂数算法实战：从暴力枚举到DFS剪枝优化
自幂数这个话题乍一看像是数学课本里那种“了解一下就行”的小知识点但我实际拿它做过一轮完整的算法练习和教学演示之后发现它特别适合用来打通“数学定义到代码实现”之间的那道墙。所谓自幂数简单说就是一个n位数它的每一位数字的n次方之和恰好等于它本身。最出名的例子是153三位数1³5³3³112527153完美闭环。这类数在圈子里常被叫做水仙花数、阿姆斯特朗数叫法不同但指向同一个东西。我写这篇东西是想把“02自幂数”这个练习项目从头到尾拆一遍——它适合刚学编程想找练手题的人也适合需要给新人讲算法思路的带教者更适合那些想弄明白“为什么暴力枚举能跑、什么时候该剪枝”的实践者。下面全部是我自己动手跑过、改过、踩过坑之后整理出来的内容不玩虚的。1. 项目整体设计与思路拆解1.1 为什么选自幂数作为算法练习载体我挑自幂数来做练习项目核心原因是它的定义足够干净但实现路径却有好几条能自然拉开难度梯度。定义里只有两个动作拆位、求幂、求和、比较。可一旦你把位数n放开问题就来了——n位数的范围是从10^(n-1)到10^n-1n稍微大一点枚举量就爆炸。这就逼着你去想能不能不枚举全部能不能利用幂次的单调性做剪枝能不能用查表把幂运算省掉对比一下其他常见的入门题比如素数判断、斐波那契自幂数的好处是它同时涉及数位操作和幂运算两个基础技能点而且结果集很小、验证起来特别直观。你跑完程序把结果往数学定义里一代对不上就是错没有模糊地带。这种“即时可验证性”对新手特别友好调试的时候心里有底。另一个我比较看重的点是自幂数天然适合做分位数讨论。一位数、两位数、三位数……每个位数区间的解的数量和分布都不一样你可以按位数分段跑观察程序在不同规模下的表现。这种“同一问题、不同规模”的对照比单纯刷一道题收获大得多。1.2 暴力枚举与剪枝优化的取舍逻辑最直接的实现就是暴力枚举对每个n位数拆位、求n次方、求和、比较。这个方案的优势是逻辑零歧义写出来基本不会错适合作为第一版基线。但它的代价也很明显——n7的时候要检查900万个七位数每个数拆7位、做7次幂运算粗算就是几千万次乘法纯Python跑起来肉眼可见地慢。那要不要一上来就上剪枝我的经验是不要。先写暴力版跑出正确结果把它当作“标准答案生成器”后面所有优化版本都拿它来对拍。这个顺序很重要我见过不少人直接写优化版结果剪枝条件写错跑出来的结果少了几个数自己还不知道因为没有基线可比。剪枝的核心思路是利用幂次和的上下界。比如你在枚举过程中已经确定了前k位剩下的位还没定那当前幂次和加上“剩余位全取9”的最大可能值如果还小于当前枚举区间的下界就可以直接砍掉这一支。反过来如果当前幂次和已经超过上界也可以提前退出。这个思路本质上是深度优先搜索加界限剪枝把“逐个数检查”变成“逐位构造”。我实测下来n≤7的时候暴力枚举还能接受n8开始就必须上剪枝了否则时间成本不成比例。这个分界线不是绝对的跟语言、机器都有关系但大致在这个量级。1.3 幂运算的预处理策略还有一个特别容易被忽略的优化点幂运算查表。自幂数的计算里0到9这十个数字的n次方会被反复用到无数次。与其每次都调pow(d, n)不如一开始就把pow_table[d] d**n算好存成一个长度10的数组后面直接索引。这个改动的收益有多大我做过对比在n7的暴力枚举里查表版本比实时pow版本快了大概三到四成。原因很简单pow函数内部有通用幂运算的逻辑分支而查表就是一次数组访问省掉了函数调用和循环乘方。对于这种“底数只有10种、指数固定”的场景查表是稳赚不赔的买卖。更进一步如果你用C或者Rust这类语言还可以把pow_table做成编译期常量连运行时初始化都省了。Python里虽然做不到编译期但模块加载时算一次存全局也完全够用。2. 核心细节解析与实操要点2.1 数位拆解的几种写法与坑拆位看着简单但写法不同坑也不同。最常见的两种一种是转字符串再逐字符转int另一种是用取模和整除循环剥位。字符串写法代码短可读性好def digits_str(num): return [int(c) for c in str(num)]但它有个隐性成本——类型转换。每个数都要走一遍int转str再转回int的流程在百万级枚举里这个开销不可忽视。而且字符串写法默认你处理的是非负整数负数得额外处理自幂数定义里一般只讨论正整数所以这点还好。取模写法更“底层”def digits_mod(num): result [] while num 0: result.append(num % 10) num // 10 return result这个写法没有类型转换纯算术操作速度快。但要注意两个细节一是得到的位数是逆序的个位在前如果你对顺序有要求得反转二是num0的情况循环一次都不进返回空列表得单独处理。我在第一版里就栽在这——忘了0这个边界结果一位数里的0没被正确识别。提示自幂数讨论通常从1开始0是否算自幂数在不同资料里有分歧0¹0形式上成立。做练习项目时建议在代码注释里明确你的约定避免结果对不上时扯皮。2.2 幂次和的累加与提前终止累加幂次和的时候有一个特别实用的技巧边加边比较超了就停。因为所有幂次都是非负的和只会越加越大。如果你已经知道当前数的上界比如它是个n位数最大就是10^n-1那一旦部分和超过这个上界后面不用算了直接判定不是自幂数。这个提前终止在暴力枚举里能省不少时间尤其是那些高位数字很大的数往往加两三项就超了。实现上就是在循环里加一个判断def is_armstrong(num, n, pow_table): total 0 temp num limit 10 ** n - 1 while temp 0: total pow_table[temp % 10] if total limit: return False temp // 10 return total num注意这里的limit用的是“n位数的最大值”而不是num本身。为什么因为我们要判断的是“和是否等于num”如果和已经超过n位数的最大可能值那它肯定不等于任何n位数提前退出是安全的。用num本身做上界也行但那样判断更频繁、收益略小用limit更宽松一点减少误杀。2.3 位数n的确定与边界处理自幂数的定义依赖位数n所以第一步永远是确定n。对于给定的数numn len(str(num))或者用循环数位数。这里有个容易翻车的地方前导零。比如数字10它是两位数但如果你的拆位逻辑把前导零也算进去就可能把位数搞错。自幂数定义里不认前导零所以位数就是有效数字的个数。另一个边界是一位数。一位数n1每位数字的1次方就是它自己所以1到9全都满足定义0¹0也满足看约定。这意味着如果你从1开始枚举一位数结果会是1、2、3、4、5、6、7、8、9全中。很多人第一次跑程序看到这个结果会愣一下以为程序写错了其实是定义使然。我在带新人的时候专门强调过这一点一位数全是自幂数这不是bug是数学事实。2.4 结果去重与排序的细节如果你是按位数分段跑最后合并结果时要注意去重。正常情况下不同位数的自幂数不会重复位数不同数值范围就不重叠但如果你在代码里对n的处理有误比如把同一个数用不同的n算了两遍就可能出现重复。稳妥的做法是最后统一放进一个set再排序输出。排序本身没什么技术含量但输出格式值得讲究。我习惯按位数分组打印每组一行这样一眼能看出每个位数区间有几个解。对于教学演示来说这种分组展示比一坨数字堆在一起清楚得多。3. 实操过程与核心环节实现3.1 第一版纯暴力基线实现先上完整的第一版代码目标只有一个——正确不管快慢。def find_armstrong_bruteforce(max_n): results {} for n in range(1, max_n 1): low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found [] for num in range(low, high 1): total 0 temp num while temp 0: d temp % 10 total d ** n temp // 10 if total num: found.append(num) results[n] found return results这段代码我建议你亲手敲一遍别复制。敲的过程中你会自然去想几个问题low为什么n1时特殊处理因为10^01但一位数从1开始0要不要算看你约定。high为什么是10^n-1因为n位数的最大值就是全9。这些细节自己推一遍比看别人写十遍都管用。跑n1到6结果应该是一位数9个1-9三位数4个153、370、371、407四位数3个1634、8208、9474五位数3个54748、92727、93084六位数1个548834。两位数没有七位数有4个1741725、4210818、9800817、9926315。这些结果你拿计算器随手验一个比如94749⁴4⁴7⁴4⁴656125624012569474对得上。3.2 第二版查表加提前终止在第一版基础上做两个改动幂表预计算、部分和超限提前退出。def find_armstrong_optimized(max_n): results {} for n in range(1, max_n 1): pow_table [d ** n for d in range(10)] low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found [] for num in range(low, high 1): total 0 temp num while temp 0: total pow_table[temp % 10] if total high: break temp // 10 else: if total num: found.append(num) results[n] found return results这里用了Python的for-else结构while正常走完没被break才进else。这个写法比较紧凑但如果你不熟悉for-else改成标志位也行可读性优先。实测n6的时候优化版比暴力版快大约一半n7的时候差距拉大到三倍左右。这个提升主要来自提前终止——七位数里大量数的幂次和在前几位就超了省掉了后面的计算。3.3 第三版按位构造的剪枝搜索到了n8以上逐个数枚举开始吃力这时候换思路不枚举数枚举数字组合。因为自幂数的幂次和只跟“每个数字出现几次”有关跟数字的排列顺序无关。比如153和351的幂次和是一样的都是1³5³3³只是数值不同。所以我们可以按“0到9各用几次”来构造总次数等于n。这个思路的搜索空间是“把n个位置分配给10个数字”的组合数比10^n小得多。具体实现用递归每层决定当前数字用几次同时维护当前幂次和与已用位数。剪枝条件当前幂次和加上“剩余位数全取9的幂”还小于目标下界或者当前幂次和已经超过上界就砍掉。def find_armstrong_dfs(n): pow_table [d ** n for d in range(10)] low 10 ** (n - 1) if n 1 else 1 high 10 ** n - 1 found set() def dfs(digit, remaining, current_sum, combo): if remaining 0: if low current_sum high: digits_of_sum sorted(str(current_sum)) if digits_of_sum sorted(combo): found.add(current_sum) return if digit 9: return max_possible current_sum remaining * pow_table[9] if max_possible low: return if current_sum high: return for count in range(remaining, -1, -1): dfs(digit 1, remaining - count, current_sum count * pow_table[digit], combo str(digit) * count) dfs(0, n, 0, ) return sorted(found)这段代码的关键在最后的验证DFS构造出的current_sum要反过去检查它的各位数字组合是否和combo一致。为什么因为DFS是按“假设用了哪些数字”来累加幂次和的但累加出来的和其实际数字组成未必和假设一致。只有一致了才说明这个和确实是由这些数字构成的才是真正的自幂数。这个“构造后回验”是组合搜索类问题的通用套路我第一次写的时候漏了这步结果多出一堆假解。n8用这个版本跑秒出结果。n9、n10也能在可接受时间内完成。再往上就得考虑更精细的剪枝或者换语言了。3.4 参数选择与性能对照把三个版本在不同n下的表现整理成表方便你判断什么时候该用哪版位数n暴力版耗时查表优化版DFS剪枝版解的个数50.1s0.1s0.1s36~0.5s~0.25s0.1s17~5s~1.5s~0.1s48不可接受~15s~0.5s39不可接受不可接受~3s410不可接受不可接受~20s1这些数字是我在一台普通笔记本上跑出来的具体值会因机器而异但量级关系是稳定的。你可以看到n≤6三个版本差别不大n7开始DFS优势明显n≥8基本只能靠DFS。这个表的意义在于帮你建立“规模感”——知道什么规模该上什么手段比死记某个算法重要得多。注意DFS版本里那个combo str(digit) * count的字符串拼接在n很大时会有内存开销。如果追求极致可以改成用计数数组传递但可读性会下降。练习项目里我建议保留字符串版清晰优先。4. 常见问题与排查技巧实录4.1 结果少了几个数怎么查这是最高频的问题。程序跑完结果比预期少第一反应往往是“剪枝剪过头了”。排查顺序我一般是这样的先关掉所有剪枝退回暴力版确认暴力版结果和数学预期一致。如果暴力版也少那问题在基础逻辑不在剪枝。基础逻辑里最常见的错是位数n算错——比如把num100的位数算成2因为拆位循环只走了两次就遇到0退出导致用2次方去算三位数。修法是拆位前先确定n或者用len(str(num))。如果暴力版对、优化版少那就是剪枝条件写错了。重点检查两个不等式方向max_possible low该砍current_sum high该砍方向反了就会误杀。我见过把写成导致边界解被砍的情况153这种刚好卡在边界的数就丢了。4.2 结果多了假解怎么定位结果多出来八成是回验环节缺失或写错。DFS版本里如果忘了检查“current_sum的数字组成是否等于combo”就会把一堆幂次和碰巧落在区间内、但数字组成对不上的数也算进去。定位方法很简单把多出来的数单独拿出来手动算它的幂次和再看这个和的数字组成和原数是否一致。不一致就是回验没做对。还有一种多解的情况是重复计数。比如DFS里对同一个数字组合的不同排列都算了一遍但最后没去重。用set存结果就能解决代价是丢失顺序输出前排个序即可。4.3 大n跑不动时的应急手段n跑到9、10以上如果机器慢或者语言效率低可以上几个应急手段。第一是换语言同样的DFS逻辑用C写n10能压到一两秒。第二是并行化按首位数字或者按数字组合的第一位分片多进程各跑各的最后合并。第三是限制搜索深度如果你只关心“有没有解”而不关心“所有解”找到第一个就可以停。不过我得说句实在话自幂数这个练习项目的价值主要在n≤8这个区间再往上更多是性能调优的炫技数学上的新东西不多。把n1到8跑通、三个版本对拍一致这个项目的核心目标就达成了。4.4 常见问题速查表现象可能原因排查动作一位数结果只有部分0的约定不明确或循环从0开始漏了检查low的取值和0的处理两位数有解位数n算错用了错误的指数打印每个候选的n值核对结果整体偏移幂表索引错位或指数用错抽查一个已知解手动验算优化版比暴力版少剪枝不等式方向反了临时关剪枝对比结果DFS版多出假解回验环节缺失检查combo与current_sum的数字组成比对大n内存暴涨字符串拼接或递归栈过深改用计数数组、增大递归限制5. 从练习到教学的延展用法5.1 用自幂数讲“定义到代码”的翻译我带新人的时候喜欢拿自幂数当第一个“完整翻译”案例。数学定义是“n位数各位n次方和等于自身”翻译成代码就是三层确定n、拆位求幂和、比较。每一层都能单独拎出来讲——确定n讲边界拆位讲循环和取模比较讲浮点陷阱这里没有因为全是整数正好可以对比讲为什么有些题不能用浮点。这个案例的好处是没有外部依赖不用装库、不用配环境打开编辑器就能写。新人写完跑出153那种“我让电脑算出了数学规律”的成就感比刷十道输入输出题都强。5.2 用版本迭代讲“先正确后优化”三个版本的演进路线本身就是一堂工程课。第一版只求对第二版做常数优化第三版换算法范式。每一步的动机都清清楚楚第一版慢是因为重复算幂所以第二版查表第二版还是逐个枚举所以第三版换组合搜索。这种“问题驱动改进”的叙事比直接甩一个最优解更能让人理解优化的来龙去脉。我通常会让学生自己先跑第一版跑到n7卡住再引导他们想“哪里在重复劳动”。大部分人能想到查表少数人能想到剪枝极少数能跳到组合搜索。这个分层正好对应不同的思维水平讨论起来有层次。5.3 延展方向其他进制与变体自幂数的定义可以平移到任意进制。二进制下的自幂数、十六进制下的自幂数都是有意思的变体。实现上只需把“10”换成进制基数“9”换成“基数-1”幂表长度跟着变。这个延展能帮你理解“十进制只是特例”对进制转换的理解也会更深。另一个变体是幂次不固定为位数比如固定用平方或者立方。固定立方的话就是“各位立方和等于自身”的数153那批还在但位数不再限制为3。这类变体的搜索空间和剪枝条件都要重新推适合作为进阶练习。6. 我踩过的几个具体坑第一个坑是0的处理。我第一版代码里一位数从0开始枚举结果0也被算进去了。数学上0¹0确实成立但很多资料不把0列为自幂数。这个分歧本身不是错错在我没在代码里明确约定导致后面跟别人的结果对不上时浪费了半天排查。现在的习惯是代码开头写一行注释明确“本实现从1开始0不计入”一劳永逸。第二个坑是幂表的初始化位置。我一开始把pow_table放在最外层循环外面想着“算一次就够了”结果n变化时表没更新用的还是上一个n的幂值跑出来的结果全乱。这个bug特别隐蔽因为小n的时候可能碰巧对比如n1和n2的某些数字幂值相同到大n才暴露。修法很简单把表放进n的循环里每个n重新算。第三个坑是DFS的递归深度。n10的时候递归深度到10层Python默认递归限制是1000够用。但如果我为了通用性把数字范围从10扩到更大比如考虑多进制深度可能上去就得调sys.setrecursionlimit。这个坑我当时没遇到是后来做变体时踩的提前说一声省得你重复。第四个坑是结果验证的偷懒。有次我图省事只拿前几个结果跟记忆里的对后面的没验结果一个剪枝边界写错中间漏了两个数直到做版本对拍才发现。教训是任何优化版本都必须和暴力基线全量对拍不能抽查。对拍代码就三行写起来不费事省下的排查时间是以小时计的。7. 完整可复现的操作清单如果你想把整个项目从头跑一遍按这个顺序来写暴力版跑n1到6记录结果手动验算至少两个解。写查表优化版和暴力版全量对拍确认结果一致记录耗时对比。写DFS剪枝版同样全量对拍重点检查n7、8的结果。把三个版本的结果整理成表观察解的个数随n的变化规律。尝试n9、10记录DFS版的耗时感受规模增长。选一个变体其他进制或固定幂次改一版验证思路迁移。每一步的产出都留着尤其是对拍记录。这些记录在写总结或者给别人讲的时候比代码本身更有说服力——它证明你不是碰巧跑对而是系统验证过。最后分享一个我常用的验证小技巧拿结果里的任意一个数用计算器或者手算把幂次和重新算一遍和原数比对。这个动作看着笨但能抓出“程序内部自洽但定义理解错”的问题。比如如果你把“各位n次方”错理解成“各位的位数次方再乘位数”程序自己跑得通但结果和数学定义对不上手算一验就露馅。自幂数这个项目数学定义就是最终裁判代码只是翻译翻译得对不对拿原文对一遍最踏实。