最近整理硬盘里压箱底的学习资料翻出一批很老很老的C程序。文件名现在看挺有意思什么puzzle73.c、brides75.c打开一看一股老式DOS编程的味道扑面而来没有带头文件main()裸奔最后还挂一个getch()等着按键才退出。其中第75题就是“新郎新娘匹配问题”。这题在很多C语言习题集里都出现过本身逻辑不难可老代码拿现在的编译器过一遍报错能给你报出七八条逻辑写法也藏着好几个容易翻车的点。我觉得正好拿它当样本聊聊怎么把复古C语言代码修到能编译、能运行、还能一眼看懂。先说清楚这道题是什么。三个新郎A、B、C三个新娘X、Y、Z三对新人要配对。已知三条消息A不和X结婚X的婚配对象不是CC不和Z结婚。问最终谁和谁是一对。题目编号之所以带个75是因为在某套流传很广的习题集里它排在第75位内容本身和数字75没有关系纯粹是题号。今天这篇不光是给答案更想把“老代码为什么会写出这样”“修的时候踩了哪些坑”“条件表达式到底该怎么翻译”这些过程完整讲一遍对刚接触C语言、或者在读老代码时一脸懵的朋友应该有点用。1. 题目原型与解题思路三个新郎三个新娘的条件组合1.1 原题描述与三条约束原题通常是这样叙述的有三个新郎分别是A、B、C三个新娘分别是X、Y、Z。已知A不和X结婚X的婚配对象不是CC不和Z结婚。这里要注意第二条“X的婚配对象不是C”和第三条“C不和Z结婚”不是同一件事。前者的主语是X意思是C不能娶X后者的主语是C意思是C不能娶Z。两条合在一起C的新娘既不能是X也不能是Z那C就只能娶Y了。这个推理过程用一句话就能说清三个新娘里排除掉两个剩下的那个就是答案。但正因为人脑能一眼推出结论很多初学者反而不理解程序为什么要用三层循环去傻傻枚举。这个矛盾恰好是学习点机器没有人那么会“看”但它可以老老实实把3×3×327种组合全部试一遍再用条件过滤出合法组合。人脑做推理机器做枚举这是两种完全不同的解问题思路。1.2 为什么这道题能在几十本教材里存活我见过不少C语言习题集从老到新类似的“婚配问题”“分房问题”“排座位问题”几乎每隔几本就会出现一次。原因是它虽然场景简单背后却覆盖了好几个核心知识点嵌套循环、逻辑表达式、排列去重、穷举法。对初学者来说没有任何一个知识点超纲但把它们组合到一起又能实实在在考到人对约束条件的表达能力。把题目再抽象一下它本质上是一个“排列约束搜索”问题三个新郎对应三个新娘等价于把0、1、2三个数字排列给A、B、C三个位置每个数字只能用一次然后在6种排列里找满足额外条件的解。这个描述不复杂却为后面升级到回溯算法埋下了伏笔。等以后遇到八皇后、数独、任务分配你会发现它们的内核和这道题一模一样。2. 复古代码“考古”DOS时代C程序在新编译器下的第一轮报错2.1 老代码现场还原要聊修复总得先有“病人”。我手头这份老代码风格非常典型大概是这个样子#include conio.h main() { char x, y, z; clrscr(); for (x X; x Z; x) for (y X; y Z; y) for (z X; z Z; z) if (x ! y y ! z x ! z x ! X z ! Z z ! X) { printf(A-%c B-%c C-%c\n, x, y, z); } getch(); }先别急着说它烂。在那个年代编译器默认把所有未声明返回类型的函数当作intmain()不写返回类型是常态conio.h提供控制台输入输出函数clrscr()清屏getch()等用户按一个任意键再结束属于当时写习题程序的标准模板。代码逻辑本身也说得通x、y、z分别表示A、B、C的新娘条件里做了三件事——保证三个新娘互不相同、A不娶X、C不娶Z和C不娶X。但这段代码放到现在的编译环境里问题一串一串地冒出来。2.2 报错清单conio、main、getch一个都跑不掉先说编译阶段。现在的主流编译器找不到conio.h因为这头文件基本是早期Windows/DOS字符界面环境特有的标准C里根本没有。紧接着main()前面没写返回类型就算编译器好心放过去也会给一堆警告。再往下走clrscr()和getch()都是没见过的函数名报错毫不客气。就算代码勉强编译过了在非Windows终端下运行时getch()可能会表现得很奇怪因为现代Linux或macOS终端默认是行缓冲模式不经过特殊设置根本收不到“任意键”的效果。还有一处隐蔽问题char型变量在循环里从X自增到Z虽然这三个字符在ASCII里连续没问题可如果哪天把题目换成新房的名字比如A、B、C这样的字母循环边界就得重新算极易出错。修复策略很简单先删掉非标准库函数再用标准输入输出替代把main()写成int main(void)最后给函数补上return 0;。这一步的目标只有一个——让程序在现代环境下先能编译、能跑起来逻辑问题放到后面再说。2.3 修复顺序先让程序能编译再让程序算得对很多新手拿到老代码第一反应是“全删了重写”。其实不用修复讲究顺序。第一步把#include conio.h改成#include stdio.h同时删掉clrscr()和getch()。第二步把main()改为int main(void)并在函数末尾加return 0;。第三步重新编译这时剩下的问题基本都是警告比如整型和字符型混用先把它们观察清楚别急着全改。第四步才是值得花时间的地方——检查原来代码里的业务逻辑是不是题目想要的意思。我自己修这类代码的习惯是编译没问题后先运行一次看输出。如果输出结果和你认为的正确答案一致再去谈优化变量命名、重构循环结构如果输出不对再回过头逐条翻译条件。要是一开始就大改数据结构很可能把“编译器报错”和“逻辑错误”混在一起排查时会非常痛苦。3. 核心代码逐行解析换一种写法就能少一堆坑3.1 第一处改动用整数下标映射新娘名字老代码用char x, y, z直接表示新娘名字好处是printf的时候省事坏处是条件判断里全是X、Z这样的字符常量稍不留神就把条件写成x ! Z之类的乌龙。更稳妥的写法是把新娘看成“0号、1号、2号”也就是用整数下标代表X、Y、Z通过数组把下标索引映射回字符#include stdio.h int main(void) { char bride[3] {X, Y, Z}; int a, b, c; for (a 0; a 3; a) { for (b 0; b 3; b) { if (a b) { continue; } for (c 0; c 3; c) { if (a c || b c) { continue; } if (a ! 0 c ! 2 c ! 0) { printf(新郎A娶新娘%c\n, bride[a]); printf(新郎B娶新娘%c\n, bride[b]); printf(新郎C娶新娘%c\n, bride[c]); printf(----\n); } } } } return 0; }变量a、b、c表示什么它们不是新郎也不是新娘而是“下标”。a代表新郎A的新娘下标b代表新郎B的新娘下标c代表新郎C的新娘下标。0对应X1对应Y2对应Z。3.2 第二处改动循环里去重避免一个新娘嫁两次三层循环的直接枚举范围是3×3×327种。可一个新娘不可能同时嫁给两个新郎所以a、b、c必须互不相同。老代码在if里用一串x ! y y ! z x ! z判断也能达到效果但把所有逻辑堆在if行里条件一多就难读。修复版把去重提前到了循环内部进入b循环时先判断a b满足就跳过。进入c循环时判断a c || b c重复就直接continue。这种写法的好处是过滤规则被拆成“互不相同”和“业务约束”两层后续想加额外条件只需要在最后那个 if 里追加不会再把所有东西搅成一团。去重的本质是“剪枝”。a等于b的情况有3种b循环直接跳过进入c循环时能被允许的三元组已经少了三分之一。虽然27这个基数太小感觉不到性能差别但这种思想放在更大规模的问题里就是指数级优化。3.3 第三处改动把三个条件写成一目了然的if最后那个条件判断是整个题目的灵魂if (a ! 0 c ! 2 c ! 0)一行三个约束每一个都对应题目原话a ! 0新郎A的新娘下标不能是0等价于A不娶Xc ! 2新郎C的新娘下标不能是2等价于C不娶Zc ! 0新郎C的新娘下标不能是0等价于X不嫁给C。这里最关键也最容易错的就是第二条题目信息“X的婚配对象不是C”。它是X视角的条件翻译到代码里应该看C的新娘是谁也就是c变量而不是看X变量的值。因为程序里压根没有独立的“X”变量X只是新娘表里的0号元素。这个“主语转换成变量”的过程就是初学者最容易翻车的一步。运行结果只有一行有效输出新郎A娶新娘Z 新郎B娶新娘X 新郎C娶新娘Y程序没有用任何人工推理纯粹靠穷举过滤就把答案掏出来了这就是机器解题的典型路径。4. 调试实录条件写错时程序会带回哪些预料外的答案4.1 现象一运行完什么都没输出很多初学者把代码敲完后运行结果一片空白。第一个要怀疑的就是条件之间产生了矛盾。比如有人把“X不嫁给C”理解成“B也不娶X”又在条件里多加了一个b ! 0那结果就是无解。为什么无解因为真实答案里B娶的就是X。多加的约束等于把正确答案也屏蔽了。这个例子告诉我们每写一个条件都要想清楚它是谁对谁的限制。题目只说了A、C两人谁不能娶谁没说B的事那就不要给B加约束。第二个常见原因是把字符常量写错。比如if (z ! X z ! Z)里z是C的新娘变量C不能娶X和Z那C只能娶Y看起来没问题。但如果变量定义的是x、y、z而打印时也用x、y、z很容易把判断的变量写混。修老代码时一定要先在纸上写清楚“x代表A的新娘”然后在所有if里盯着x出现的地方逐一核对。4.2 现象二输出一组“看似合理”的错误答案比“没有输出”更迷惑的是程序输出了结果但答案是错的。我见过一个典型例子if (x ! X y ! X z ! Z)粗看没什么问题A不娶XB不娶XC不娶Z。运行结果会输出什么呢手推一下这组约束下会得到“A娶ZB娶YC娶X”这样的组合。因为条件里并没有限制C不能娶X那个“X不嫁给C”被错误地安到了B头上。程序内部逻辑自洽输出也像模像样如果不拿答案比对根本不知道它已经跑偏了。用代码验证一下前面修复版如果把c ! 0错写成b ! 0输出就变成A娶Z、B娶Y、C娶X还是能打印出完整的一行结果。这非常坑人。所以调试这类逻辑题不能只看“有没有输出”要先把推理结果算出来再对照程序输出。4.3 通用调试法打印每一层循环的当前下标遇到这种问题我常用的笨办法是在循环里临时加打印看看每次进入if之前a、b、c到底是多少。比如在最内层循环开头放一句printf(a%d b%d c%d 通过%d\n, a, b, c, a ! 0 c ! 2 c ! 0);这样就能看到27种组合中每一种被通过还是被过滤再对比题目条件很快能定位是哪条判断卡错了。很多人不愿意用打印调试觉得太低效但对付这种小规模穷举题打印是所有方式里最快、最直观的。先把唯一的正确组合找出来再反向检查条件比盯着代码发呆有用得多。5. 从3对扩展到N对把穷举升级成回溯5.1 为什么三层循环的写法在N变大时撑不住3对新郎新娘用三层循环没问题如果题目变成4对呢四层循环勉强能写。变成10对呢循环层数是动态的根本没法编码。就算勉强用10层嵌套写出来10的10次方等于100亿次枚举程序也要跑到天荒地老。此时要把“固定嵌套”改成“递归层数”。N个新郎对应N个新娘本质上是在全排列里做约束搜索。全排列的数量是N的阶乘10的阶乘是36288003的阶乘是6。规模一下子可接受了许多因为通过“每个新娘只能选一次”这个限制搜索空间从N的N次方降到了N的阶乘。递归回溯就是在每一层尝试给第pos个新郎分配一个还没用过的新娘下标如果这个分配满足已知条件就继续往下走不满足就换一个试试走到第N层说明找到一组完整方案。5.2 递归回溯框架代码把刚才的婚配问题用回溯重写结构更清晰也更接近通用解法#include stdio.h int bride[20]; int used[20]; int n; int total; int ok(int pos) { if (pos 0 bride[0] 0) return 0; // A不娶X if (pos 2 bride[2] 2) return 0; // C不娶Z if (pos 2 bride[2] 0) return 0; // C不娶X即X不嫁C return 1; } void dfs(int pos) { if (pos n) { for (int i 0; i n; i) { printf(%c -- %c , A i, X bride[i]); } printf(\n); total; return; } for (int i 0; i n; i) { if (used[i]) { continue; } bride[pos] i; if (!ok(pos)) { continue; } used[i] 1; dfs(pos 1); used[i] 0; } } int main(void) { n 3; total 0; dfs(0); printf(共 %d 组解\n, total); return 0; }核心在于dfs(pos)函数里的三步操作先尝试给第pos个新郎分配新娘下标i再检查是否违反约束不违反就标记used并向下递归回来时记得把used解除标记。used数组保证每个新娘下标在同一分支里只使用一次这就完成了去重。5.3 剪枝与位运算优化回溯代码里“检查再进入”就是剪枝。更早地发现某条路径不可能有解就能更早退出。比如在原题中pos等于2时C的新娘不能是0我们等递归到第三层才检查。如果改成提前判断可以在进入下一层之前就把不合法分支砍掉搜索树会更小。还有一种古典优化是把used数组换成整数位掩码。第i位表示新娘i是否已被使用用int mask代替数组int dfs(int pos, int mask) { if (pos n) { ... } for (int i 0; i n; i) { if (mask (1 i)) continue; if (不满足约束) continue; dfs(pos 1, mask | (1 i)); } }位运算的好处除了省内存还有一个隐藏价值递归传参时不用再手动恢复现场。因为mask是按值传递的子函数怎么改都不会影响父函数的值。这段位运算代码在N比较小的时候非常舒服也适合拿来理解“状态压缩”这个概念为以后打算法基础做铺垫。6. 常见问题速查表老代码修复的通用避坑清单修复这类复古代码很多坑是重复出现的。我把高频问题整理成了一个速查表改任何老C程序都能对照着看。错误现象可能原因解决办法编译报错找不到conio.h非标准头文件删除替换成stdio.hmain前面没写返回类型老式写法改成int main(void)末尾加return 0;getch()、clrscr()未声明非标准控制台函数删除需要暂停可用getchar()或空循环等待程序无输出条件互相矛盾检查是否有额外错误约束用打印中间结果定位输出结果与答案不符条件的主语映射错把“谁不能娶谁”翻译到具体变量上再核对出现重复输出没做去重判断检查a、b、c是否互不相同用char变量做循环自增字符边界容易出错改成整数下标用数组映射回字符除了表格还有两条心得值得单独说。第一条老代码里的变量名普遍很短x、y、z满天飞。修复时不要心疼大胆改成a、b、c或者更有语义的names改完你会发现逻辑本身清楚了一大截。好的变量名不是锦上添花是帮你发现错误的第一道防线。第二条不要迷信“老代码能跑就是对的”。当年编译器比较宽松很多不规范写法只是碰巧能过并不代表代码正确。尤其遇到void main()、全局变量满天飞、函数没有返回值这类问题该改的都要改掉。修复老代码的目标不是让它回到当年的编译环境而是让它以清晰、规范的面貌继续发挥作用。最后说一点我自己的体会。修这种老代码修得多了慢慢养成一个习惯看到题目先不动手先在纸上用中文把约束条件写清楚再映射到变量。像这道题“X的婚配对象不是C”这句话很多人第一反应会把X当成程序变量写出来就变成了x ! C那就完全跑偏了——X只是新娘的名字不是程序里的下标变量。这种错误正是复古代码里最容易埋的雷。如果你也拿到一批老C程序别怕报错一条一条来先管头文件再管main再管函数调用最后盯逻辑。修完之后你会发现几十年前的老题目其实一点都不过时。
