前阵子刷某高校《计算机概论和程序设计基础》这门MOOC课程循环练习那一节配了一道非常经典的题——完美立方。第一眼看过去真不难枚举四个整数判断立方等式成立就行。可真正动手才发现题面里那些不起眼的限制条件比如b大于1、b小于等于c小于等于d每一条都在帮你避免重复输出也在悄悄考察你对循环边界的理解。更别说很多人习惯用pow函数判断立方相等样例能跑通提交却经常挂在浮点比较上。这篇文章我把完美立方从题目解读、暴力实现、剪枝优化到提交踩坑完整过一遍正在刷这门课的同学可以对照着看自学C语言想找几道经典枚举题练手的也同样适用。1. 完美立方题目在说什么从数学等式到程序约束1.1 题面与输出的标准格式完美立方的标准表述是给定一个正整数N输出所有满足a³ b³ c³ d³的组合。其中a的范围是2到Nb、c、d为正整数并且常见题面会额外要求1 b ≤ c ≤ d。部分平台可能不写b1这个条件但绝大多数在线评测都沿用这个约定。我第一次做这道题时下意识忽略了b1的限制心想1也是正整数为什么不能从1开始枚举后来对照标准输出才发现b从2开始是为了去掉一类没有讨论价值的退化组合。b1时1³加上另外两个立方数即使能凑出某个立方数学上也显得很不自然所以传统题意直接把它排除在外。你要是非从1开始跑输出里会出现一堆和标准答案对不上的奇怪行。以N24为例输出会包含类似下面这些行节选Cube 6, Triple (3,4,5) Cube 12, Triple (6,8,10) Cube 18, Triple (2,12,16) Cube 18, Triple (9,12,15) Cube 19, Triple (3,10,18) Cube 20, Triple (7,14,17) Cube 24, Triple (12,16,20)注意Cube 18出现了两行说明同一个a可能对应多组不同的b、c、d组合。程序必须把所有满足条件的组合全部找出来而不是找到一组就break——很多初学者在这里犯迷糊以为每组a最多一个解结果输出少了好几行。1.2 三条限制条件背后的实际作用b 1、b ≤ c ≤ d、b、c、d都小于a这三条约束看起来是额外的麻烦实际上每一条都承担着明确职责。先看b 1。它把b直接从整数范围中剔除掉缩小了搜索空间。虽然单看少枚举一个值不算什么但在四重循环里每一层少一点总运算量的减少是相乘关系。再看b ≤ c ≤ d。这是整道题去重的核心。如果没有这条非降序约束(3,4,5)、(4,3,5)、(5,3,4)这些本质相同的组合会被当成不同组合全部输出同一组数字被排列成6份判题系统直接判你输出多余。很多人在这一步WA到怀疑人生其实就是没有理解“无序组合”和“有序四元组”的区别。最后是b、c、d都小于a。这个条件其实是由等式本身天然推出的a³等于三个正立方数之和如果b等于a那右边剩下c³d³必须为0这在正整数范围内不可能发生。所以b、c、d的最大合法值都只能是a-1。1.3 这道题到底在考什么题目本身代码量不大但它集中考察了三件事第一你能不能把数学不等式准确翻译成循环边界第二你懂不懂用非降序来去重第三你有没有浮点数比较的风险意识。很多人在课程后半段学指针、学链表时如鱼得水反而在这类基础题上反复WA原因就是这三个点没有真正想透。2. 暴力枚举第一版循环边界是怎么推出来的2.1 四个循环变量的取值范围理解了约束条件循环怎么写其实已经水到渠成。直接用一张表说明四个变量的取值逻辑变量起点终点理由a2Na是最外层立方数从2开始最大到Nb2a-1b需要大于1且小于acba-1c要满足c≥b且小于adca-1d要满足d≥c且小于a很多人写循环时容易把终点写成a心里想着反正等式不成立就不会输出。但边界写对的好处不只是少几次循环更重要的是让程序逻辑和题目描述严丝合缝别人review代码时一眼能看出你理解没理解。退一步说如果哪天条件变成了允许ba你的代码不会因为边界写死而出问题。2.2 第一版完整C代码#include stdio.h int main() { int n; scanf(%d, n); for (int a 2; a n; a) { for (int b 2; b a; b) { for (int c b; c a; c) { for (int d c; d a; d) { if (a * a * a b * b * b c * c * c d * d * d) { printf(Cube %d, Triple (%d,%d,%d)\n, a, b, c, d); } } } } } return 0; }这段代码的逻辑一句话就能说清让a从2走到N对每个a枚举所有满足b≤c≤d且都小于a的b、c、d组合判断等式是否成立。注意c从b开始、d从c开始这是保证非降序的关键。代码里没有任何break因为一个a可能对应多个解必须把内层循环全部走完才不漏解。2.3 为什么判断式写aaa而不是pow很多教程喜欢写pow(a, 3)但pow返回的是double类型。double存小整数时看起来精确一旦数字变大或者经历多次运算就可能出现类似999.9999999的舍入结果。你用去比较两个浮点数本质上是在赌舍入误差的方向运气好能过运气不好就WA。最稳妥的做法就是老老实实用aaa三个整数乘法精确且直观。如果实在担心溢出可以先转成long long再乘这一点我们放到第4节展开。3. 从O(N^4)到O(N^3)三个枚举加一个查找3.1 四重循环的规模估算听到“四重循环”很多人会本能觉得性能不行但完美立方这道题在经典数据范围下四重循环完全够用。我们粗略估算一下a有N-1个取值b平均约a/2个取值c和d也大约在a/2量级整体运算量接近N⁴/16。N估算循环量表现24约几十万次瞬间出结果100约几百万次瞬间出结果500约4亿次能跑但明显变慢1000约60亿次不建议纯暴力所以这道题的教学点其实有两层第一层是暴力能过就别想着上复杂算法第二层是跑通暴力之后值得再想一想能不能去掉一层循环。两件事不矛盾先暴力验证思路再优化打磨代码。3.2 把第四个变量从枚举变成查找等式的结构非常漂亮把d移到等式一边可以得到a³ - b³ - c³ d³。给定a、b、c之后右边d的三次方是一个确定的数。那我们完全不需要再枚举d只需要问这个确定的数是不是某个整数的立方如果是d就等于那个整数。具体做法分两步先预处理一张从1到N的立方数表再用二分查找去这张表里找目标值。因为立方数表单调递增二分查找非常合适。这样一来四层循环变成三层循环加一次查找时间复杂度从O(N⁴)降到O(N³ logN)如果继续用标记数组连logN都能去掉。优化版代码如下#include stdio.h #define MAXN 105 int cube[MAXN]; // 二分查找 target 在 cube[1..n] 中的下标找不到返回 -1 int findIndex(int target, int n) { int left 1, right n; while (left right) { int mid (left right) / 2; if (cube[mid] target) return mid; else if (cube[mid] target) left mid 1; else right mid - 1; } return -1; } int main() { int n; scanf(%d, n); for (int i 1; i n; i) { cube[i] i * i * i; } for (int a 2; a n; a) { for (int b 2; b a; b) { for (int c b; c a; c) { int target a * a * a - b * b * b - c * c * c; int d findIndex(target, n); if (d c) { printf(Cube %d, Triple (%d,%d,%d)\n, a, b, c, d); } } } } return 0; }这段代码里有一个非常容易被忽略的关键判断if (d c)。在朴素四重循环里d天然从c开始枚举非降序自动满足不需要额外判断。但在优化版里d是查找出来的可能小于c。如果不加d c这个判断同一组数字会因为枚举顺序不同而被重复输出。比如某些组合里你枚举到小的c时查出了大的d输出一次后面枚举到大的c时又查出了小的d本来应该跳过却因为少了这个判断又输出一次。这个细节几乎每个从暴力版改成优化版的人都会踩一次。3.3 再进一步用哈希表把查找变成O(1)二分查找已经够用但如果你想把N继续放大还可以把立方数表换成标记数组用空间换时间让查找变成O(1)。更极端一点的思路是提前枚举所有b、c的立方和存入哈希表然后对每个a、d检查a³-d³是否在表中命中。这样就牵扯到预处理、哈希冲突、内存占用等一系列更复杂的问题属于这道题面向进阶的延伸方向。初学阶段能把二分版本想明白就已经比大多数“只会四重循环”的同学高一个身位了。4. 提交必看格式、类型与去重三座大山4.1 pow函数的浮点比较之坑这是我在MOOC习题讨论区里见过最多的一种WA原因。有人图省事直接把判断写成if (pow(a,3) pow(b,3) pow(c,3) pow(d,3))本地样例能跑通一提交就失败。原因不复杂pow返回double而double在数值较大时会引入舍入误差例如某些环境下pow(6,3)的结果可能不是216.0而是215.9999999或216.0000001。整数与浮点数做相等比较本质是在赌误差方向这是程序设计里绝不能容忍的写法。所有整数运算都应该用整数类型完成。4.2 aaa会不会溢出从int到long long另一个容易被忽略的问题是整数溢出。题目N100时100³1000000int完全装得下。但如果你把代码搬到N1000的变体题1000³1000000000已经靠近int上限等号右边三个立方数相加更是直接超过21亿溢出风险立刻出现。稳妥做法是把参与乘方的变量声明成long long或者在C语言里用1LL * a * a * a这种写法强制把第一个乘数变成long long避免整型提升带来的一系列问题。4.3 输出格式和非降序的重复问题输出格式是很多初学者的噩梦。判题系统对行末空格有时候宽容、有时候严格建议永远不要赌这种宽容。把printf里的格式串直接复制样例是最省事的做法英文逗号、空格位置都保持一致。常见错误表现修复方式忘记b≤c≤d同一组数字输出6次循环初值必须cb、dc优化版不加dc部分组合重复输出查找后判断dcprintf格式少了逗号或空格判题报格式错误格式串照抄样例用了中文标点输出无法匹配全部换成英文半角标点如果你用的是优化版因为d是查找出来的输出顺序理论上可能与朴素版不完全一致。但只要外层a、b、c都是升序枚举输出自然就满足题目要求的字典序不需要额外排序。5. 这道题真正想教你的枚举题的通用解题框架5.1 枚举题三问搜什么、怎么搜、怎么不重复完美立方是枚举题的典型代表。做这一类题我习惯先问自己三个问题第一搜索空间是什么对完美立方来说就是所有满足约束的四元组范围由N和不等式共同决定。第二按什么顺序搜这里要求非降序所以循环嵌套的初值跟着上一层变量走。第三如何避免重复靠b≤c≤d这一条约束就够但当你改造算法时要重新检查这个约束有没有被破坏。这个三问框架可以套在很多题目上水仙花数、完全数、自守数本质上都是“把数学性质翻译成搜索程序”。你积累的枚举题越多就会越习惯在做任何循环嵌套之前先花十秒钟想清楚这三个问题而不是直接开写。5.2 与课程里同类题目的横向对比这门MOOC课程的练习里常常同时出现一批类似的数字题。水仙花数是枚举100到999判断各位立方和是否等于自身完全数是枚举因子并累加判断累加值是否等于原数自守数是枚举平方后看尾部是否等于原数。这些题难度都不高但方法完全一致确定范围、设计枚举顺序、剪枝去重。把完美立方吃透等于把这一整类题的通法掌握了。以后遇到“abc def gh”这类数字谜题底层还是同一套思路——只是搜索空间变成了字母到数字的映射复杂度分析方法依然相通。5.3 我的学习体会与建议说实话第一次跑通完美立方时我没多大成就感四重循环太直白感觉就是“让电脑傻算”。但后来我强迫自己写了优化版才体会到枚举转查找这个过程的妙处你不得不去观察数学等式的结构而不是满足于让CPU去硬扛。这种“用数学推理减少搜索量”的意识才是算法感觉的真正起点。我的建议是完美立方这道题值得写两遍第一遍用暴力版本验证思路确保边界和输出去重完全正确第二遍用查找版本体会优化带来的复杂度下降。然后顺手把课程里同章节的水仙花数、完全数都做一遍。等这一套组合拳打完循环和枚举这一关就算真正过了后面再学递归、回溯这些更复杂的内容时你会感谢现在愿意多写一遍的自己。