自幂数算法实战：从暴力枚举到DFS剪枝优化

自幂数这个话题，乍一看像是数学课本里那种“了解一下就行”的小知识点，但我实际拿它做过一轮完整的算法练习和教学演示之后，发现它特别适合用来打通“数学定义到代码实现”之间的那道墙。所谓自幂数，简单说就是一个n位数，它的每一位数字的n次方之和恰好等于它本身。最出名的例子是153：三位数，1³+5³+3³=1+125+27=153，完美闭环。这类数在圈子里常被叫做水仙花数、阿姆斯特朗数，叫法不同但指向同一个东西。我写这篇东西，是想把“02自幂数”这个练习项目从头到尾拆一遍——它适合刚学编程想找练手题的人，也适合需要给新人讲算法思路的带教者，更适合那些想弄明白“为什么暴力枚举能跑、什么时候该剪枝”的实践者。下面全部是我自己动手跑过、改过、踩过坑之后整理出来的内容，不玩虚的。

1. 项目整体设计与思路拆解

1.1 为什么选自幂数作为算法练习载体

我挑自幂数来做练习项目，核心原因是它的定义足够干净，但实现路径却有好几条，能自然拉开难度梯度。定义里只有两个动作：拆位、求幂、求和、比较。可一旦你把位数n放开，问题就来了——n位数的范围是从10^(n-1)到10^n-1，n稍微大一点，枚举量就爆炸。这就逼着你去想：能不能不枚举全部？能不能利用幂次的单调性做剪枝？能不能用查表把幂运算省掉？

对比一下其他常见的入门题，比如素数判断、斐波那契，自幂数的好处是它同时涉及数位操作和幂运算两个基础技能点，而且结果集很小、验证起来特别直观。你跑完程序，把结果往数学定义里一代，对不上就是错，没有模糊地带。这种“即时可验证性”对新手特别友好，调试的时候心里有底。

另一个我比较看重的点是，自幂数天然适合做分位数讨论。一位数、两位数、三位数……每个位数区间的解的数量和分布都不一样，你可以按位数分段跑，观察程序在不同规模下的表现。这种“同一问题、不同规模”的对照，比单纯刷一道题收获大得多。

1.2 暴力枚举与剪枝优化的取舍逻辑

最直接的实现就是暴力枚举：对每个n位数，拆位、求n次方、求和、比较。这个方案的优势是逻辑零歧义，写出来基本不会错，适合作为第一版基线。但它的代价也很明显——n=7的时候要检查900万个七位数，每个数拆7位、做7次幂运算，粗算就是几千万次乘法，纯Python跑起来肉眼可见地慢。

那要不要一上来就上剪枝？我的经验是不要。先写暴力版，跑出正确结果，把它当作“标准答案生成器”，后面所有优化版本都拿它来对拍。这个顺序很重要，我见过不少人直接写优化版，结果剪枝条件写错，跑出来的结果少了几个数自己还不知道，因为没有基线可比。

剪枝的核心思路是利用幂次和的上下界。比如你在枚举过程中，已经确定了前k位，剩下的位还没定，那当前幂次和加上“剩余位全取9”的最大可能值，如果还小于当前枚举区间的下界，就可以直接砍掉这一支。反过来，如果当前幂次和已经超过上界，也可以提前退出。这个思路本质上是深度优先搜索加界限剪枝，把“逐个数检查”变成“逐位构造”。

我实测下来，n≤7的时候暴力枚举还能接受，n=8开始就必须上剪枝了，否则时间成本不成比例。这个分界线不是绝对的，跟语言、机器都有关系，但大致在这个量级。

1.3 幂运算的预处理策略

还有一个特别容易被忽略的优化点：幂运算查表。自幂数的计算里，0到9这十个数字的n次方会被反复用到无数次。与其每次都调pow(d, n)，不如一开始就把pow_table[d] = d**n算好，存成一个长度10的数组，后面直接索引。

这个改动的收益有多大？我做过对比，在n=7的暴力枚举里，查表版本比实时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

这个写法没有类型转换，纯算术操作，速度快。但要注意两个细节：一是得到的位数是逆序的（个位在前），如果你对顺序有要求得反转；二是num=0的情况循环一次都不进，返回空列表，得单独处理。我在第一版里就栽在这——忘了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。对于给定的数num，n = len(str(num))或者用循环数位数。这里有个容易翻车的地方：前导零。比如数字10，它是两位数，但如果你的拆位逻辑把前导零也算进去，就可能把位数搞错。自幂数定义里不认前导零，所以位数就是有效数字的个数。

另一个边界是一位数。一位数n=1，每位数字的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为什么n=1时特殊处理？因为10^0=1，但一位数从1开始，0要不要算看你约定。high为什么是10^n-1？因为n位数的最大值就是全9。这些细节自己推一遍，比看别人写十遍都管用。

跑n=1到6，结果应该是：一位数9个（1-9），三位数4个（153、370、371、407），四位数3个（1634、8208、9474），五位数3个（54748、92727、93084），六位数1个（548834）。两位数没有，七位数有4个（1741725、4210818、9800817、9926315）。这些结果你拿计算器随手验一个，比如9474：9⁴+4⁴+7⁴+4⁴=6561+256+2401+256=9474，对得上。

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，改成标志位也行，可读性优先。

实测n=6的时候，优化版比暴力版快大约一半；n=7的时候差距拉大到三倍左右。这个提升主要来自提前终止——七位数里大量数的幂次和在前几位就超了，省掉了后面的计算。

3.3 第三版：按位构造的剪枝搜索

到了n=8以上，逐个数枚举开始吃力，这时候换思路：不枚举数，枚举数字组合。因为自幂数的幂次和只跟“每个数字出现几次”有关，跟数字的排列顺序无关。比如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是按“假设用了哪些数字”来累加幂次和的，但累加出来的和，其实际数字组成未必和假设一致。只有一致了，才说明这个和确实是由这些数字构成的，才是真正的自幂数。这个“构造后回验”是组合搜索类问题的通用套路，我第一次写的时候漏了这步，结果多出一堆假解。

n=8用这个版本跑，秒出结果。n=9、n=10也能在可接受时间内完成。再往上就得考虑更精细的剪枝或者换语言了。

3.4 参数选择与性能对照

把三个版本在不同n下的表现整理成表，方便你判断什么时候该用哪版：

这些数字是我在一台普通笔记本上跑出来的，具体值会因机器而异，但量级关系是稳定的。你可以看到，n≤6三个版本差别不大，n=7开始DFS优势明显，n≥8基本只能靠DFS。这个表的意义在于帮你建立“规模感”——知道什么规模该上什么手段，比死记某个算法重要得多。

注意：DFS版本里那个combo + str(digit) * count的字符串拼接，在n很大时会有内存开销。如果追求极致，可以改成用计数数组传递，但可读性会下降。练习项目里我建议保留字符串版，清晰优先。

4. 常见问题与排查技巧实录

4.1 结果少了几个数怎么查

这是最高频的问题。程序跑完，结果比预期少，第一反应往往是“剪枝剪过头了”。排查顺序我一般是这样的：

先关掉所有剪枝，退回暴力版，确认暴力版结果和数学预期一致。如果暴力版也少，那问题在基础逻辑，不在剪枝。基础逻辑里最常见的错是位数n算错——比如把num=100的位数算成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写，n=10能压到一两秒。第二是并行化，按首位数字或者按数字组合的第一位分片，多进程各跑各的，最后合并。第三是限制搜索深度，如果你只关心“有没有解”而不关心“所有解”，找到第一个就可以停。

不过我得说句实在话，自幂数这个练习项目的价值主要在n≤8这个区间，再往上更多是性能调优的炫技，数学上的新东西不多。把n=1到8跑通、三个版本对拍一致，这个项目的核心目标就达成了。

4.4 常见问题速查表

5. 从练习到教学的延展用法

5.1 用自幂数讲“定义到代码”的翻译

我带新人的时候，喜欢拿自幂数当第一个“完整翻译”案例。数学定义是“n位数，各位n次方和等于自身”，翻译成代码就是三层：确定n、拆位求幂和、比较。每一层都能单独拎出来讲——确定n讲边界，拆位讲循环和取模，比较讲浮点陷阱（这里没有，因为全是整数，正好可以对比讲为什么有些题不能用浮点）。

这个案例的好处是没有外部依赖，不用装库、不用配环境，打开编辑器就能写。新人写完跑出153，那种“我让电脑算出了数学规律”的成就感，比刷十道输入输出题都强。

5.2 用版本迭代讲“先正确后优化”

三个版本的演进路线，本身就是一堂工程课。第一版只求对，第二版做常数优化，第三版换算法范式。每一步的动机都清清楚楚：第一版慢是因为重复算幂，所以第二版查表；第二版还是逐个枚举，所以第三版换组合搜索。这种“问题驱动改进”的叙事，比直接甩一个最优解更能让人理解优化的来龙去脉。

我通常会让学生自己先跑第一版，跑到n=7卡住，再引导他们想“哪里在重复劳动”。大部分人能想到查表，少数人能想到剪枝，极少数能跳到组合搜索。这个分层正好对应不同的思维水平，讨论起来有层次。

5.3 延展方向：其他进制与变体

自幂数的定义可以平移到任意进制。二进制下的自幂数、十六进制下的自幂数，都是有意思的变体。实现上只需把“10”换成进制基数，“9”换成“基数-1”，幂表长度跟着变。这个延展能帮你理解“十进制只是特例”，对进制转换的理解也会更深。

另一个变体是幂次不固定为位数，比如固定用平方或者立方。固定立方的话，就是“各位立方和等于自身”的数，153那批还在，但位数不再限制为3。这类变体的搜索空间和剪枝条件都要重新推，适合作为进阶练习。

6. 我踩过的几个具体坑

第一个坑是0的处理。我第一版代码里，一位数从0开始枚举，结果0也被算进去了。数学上0¹=0确实成立，但很多资料不把0列为自幂数。这个分歧本身不是错，错在我没在代码里明确约定，导致后面跟别人的结果对不上时浪费了半天排查。现在的习惯是：代码开头写一行注释，明确“本实现从1开始，0不计入”，一劳永逸。

第二个坑是幂表的初始化位置。我一开始把pow_table放在最外层循环外面，想着“算一次就够了”，结果n变化时表没更新，用的还是上一个n的幂值，跑出来的结果全乱。这个bug特别隐蔽，因为小n的时候可能碰巧对（比如n=1和n=2的某些数字幂值相同），到大n才暴露。修法很简单，把表放进n的循环里，每个n重新算。

第三个坑是DFS的递归深度。n=10的时候递归深度到10层，Python默认递归限制是1000，够用。但如果我为了通用性把数字范围从10扩到更大（比如考虑多进制），深度可能上去，就得调sys.setrecursionlimit。这个坑我当时没遇到，是后来做变体时踩的，提前说一声省得你重复。

第四个坑是结果验证的偷懒。有次我图省事，只拿前几个结果跟记忆里的对，后面的没验，结果一个剪枝边界写错，中间漏了两个数，直到做版本对拍才发现。教训是：任何优化版本都必须和暴力基线全量对拍，不能抽查。对拍代码就三行，写起来不费事，省下的排查时间是以小时计的。

7. 完整可复现的操作清单

如果你想把整个项目从头跑一遍，按这个顺序来：

1. 写暴力版，跑n=1到6，记录结果，手动验算至少两个解。
2. 写查表优化版，和暴力版全量对拍，确认结果一致，记录耗时对比。
3. 写DFS剪枝版，同样全量对拍，重点检查n=7、8的结果。
4. 把三个版本的结果整理成表，观察解的个数随n的变化规律。
5. 尝试n=9、10，记录DFS版的耗时，感受规模增长。
6. 选一个变体（其他进制或固定幂次）改一版，验证思路迁移。

每一步的产出都留着，尤其是对拍记录。这些记录在写总结或者给别人讲的时候，比代码本身更有说服力——它证明你不是碰巧跑对，而是系统验证过。

最后分享一个我常用的验证小技巧：拿结果里的任意一个数，用计算器或者手算把幂次和重新算一遍，和原数比对。这个动作看着笨，但能抓出“程序内部自洽但定义理解错”的问题。比如如果你把“各位n次方”错理解成“各位的位数次方再乘位数”，程序自己跑得通，但结果和数学定义对不上，手算一验就露馅。自幂数这个项目，数学定义就是最终裁判，代码只是翻译，翻译得对不对，拿原文对一遍最踏实。