前几天整理老硬盘里的旧资料时翻出一个叫79_wine.c的文件。注释只有一行“79 - Poisson wine game”。我隐约记得这是大学时期从BBS上抄下来的当时觉得“泊松分酒”这个名字很高级真正打开一看代码风格相当远古全大写变量、缩进混乱、switch里到处是goto还有一大片的全局数组。顺手用gcc编译了一下警告刷了半屏跑起来更是直接翻车。这篇博文就是完整的C语言代码修复与解析记录围绕这份复古的“79泊松分酒”代码展开。我会先讲这个程序到底要做什么再拆解泊松分酒的核心算法然后一步步定位并修复原代码里的严重Bug最后给出一份重构后的现代C实现并聊聊维护旧代码的一些实在经验。如果你也在学C语言、接过老项目或者想通过一个具体例子弄懂状态搜索和数组越界这篇应该对你有用。这份代码让我想起很多初学者都会遇到的情况程序能编译但一运行就错错得毫无规律又死活找不到原因。实际上大部分问题都出在状态管理、数组下标和搜索判重上和语言新不新关系不大。我们用这份古董代码当“标本”刚好能把这些问题讲透。1. 我为什么会捡到这份79泊松分酒老代码1.1 从旧硬盘里翻出来的文件文件不大只有两百多行但第一眼看到时我整个人是懵的。全局变量从int a,b,c,d;一路定义到int bz[1000];函数名清一色用拼音缩写dbjg()、pd()、jgfx()没有注释。唯一可读的是顶部几行/* 79_wine.c */ /* 79 - poisson wine game */“79”到底指什么像这种老代码里数字通常有两种含义一是原题出处二是指定版本。我倾向于认为它是某个教材或习题集上的题目编号因为泊松分酒最经典的语境就是“有一瓶8升酒、一个5升杯和一个3升杯怎么量出4升酒”这在国内教材里往往被放在“回溯法”或“穷举法”章节题号79很合理。读这种代码不能直接一头扎进去得先弄清它的输入和输出。我试着运行了一下程序会提示please input target volume:输入4之后它几乎瞬间输出了一堆倒酒步骤但仔细一看步骤之间完全矛盾——上一步刚把5升杯倒满下一步又把同一个杯子“倒回”8升瓶循环往复永远到不了目标状态。1.2 先看一眼它想干什么泊松分酒问题本质上是这样的有三个容器容量分别记为v[0]、v[1]、v[2]初始状态可以是任意合法状态比如最大的容器装满其余为空。每一次操作只能做一件事把某个容器中的酒倒入另一个容器直到源容器为空或者目标容器被装满。目标是从初始状态出发经过一系列倒酒操作让某一个容器中的酒量等于指定值target。对于8、5、3这三个容量从状态 (8, 0, 0) 出发目标得到4升是一个经典的可解实例。如果不限制步骤数解一定存在如果要求步骤最短就要用广度优先搜索。这份复古代码用的也是搜索思路但它把搜索的“去重”环节做坏了导致状态反复横跳。1.3 先说结论代码能跑但不能信我后来花了大概一个晚上把这份代码从头到尾摸了一遍。归纳起来它有三个层次的毛病第一层是“卫生问题”函数声明缺失、未使用的变量满天飞这类问题不致命但会污染阅读。第二层是“算法问题”倒酒操作的转移逻辑写错导致某些可能状态根本到达不了或者到达了又被错误地覆盖。第三层是“灾难问题”状态数组越界访问未初始化数据最后程序输出的“解”其实建立在随机内存之上你根本无法信任。后面会详细拆解这些问题。但先别急着否定这份代码——它的核心骨架其实是正确的能看出作者理解“搜索状态”这一关键概念只是实现细节全部踩坑。这恰好是很多C语言学习者的共同写照思路对一写就错。所以修复它比从头写一份更有价值。2. 泊松分酒问题的数学与算法拆解2.1 倒酒问题的标准定义与状态空间在动手修代码之前必须把问题本身建模清楚。一个状态用三元组(x, y, z)表示三个容器中的当前酒量其中x对应容量v[0]的容器y对应v[1]z对应v[2]。所有状态必须满足两个约束每个容器的酒量大于等于0且小于等于自己的容量三个容器酒量之和等于初始酒量总和因为没有洒酒。所以对于容量8、5、3初始总量为8状态空间大小是9 * 6 * 4 216。当然并非所有组合都满足总量为8但哪怕是216个状态对于现代计算机来说也是小菜一碟。接下来定义操作。从状态(x, y, z)出发任选两个不同的容器 A 和 B执行“从A倒入B”可倒入量 min(A中当前酒量, B的剩余容量)如果可倒入量为0说明操作无效状态不变。每个状态最多有3 * 2 6种倒法不考虑自身倒自身。这样整个问题就变成了一个有向图上的路径搜索问题起点是初始状态终点是任一“任一杯酒量等于target”的状态边的权值都是1求最短路径。2.2 为什么必须用状态判重而不是无条件递归最容易想到的办法是DFS递归遍历所有可能的倒法从当前状态出发依次尝试6种操作进入新状态后继续递归直到找到目标状态。但如果不在递归前做状态去重会发生什么我们模拟一下初始状态(8, 0, 0)第一个操作可能是“8升瓶倒入5升瓶”得到(3, 5, 0)。然后下一个状态继续尝试操作其中有一项是“5升瓶倒回8升瓶”于是又回到(8, 0, 0)。回到初始状态后它又会尝试“倒入5升瓶”无限循环永远不会结束。没有判重的搜索就像在迷宫里走路却不知道标记已经走过的路必然转圈。这份复古代码用的正是“边递归边回溯”的思路但它在递归入口处没有把当前状态标记为“已访问”在递归结束回溯后也没有正确地取消标记结果就是死循环。正确做法是维护一个visited数组每个状态全局只处理一次在BFS里状态一旦入队就标记再也不会重复入队在DFS里进入节点时标记离开节点时取消标记因为可能走另一条路径但必须小心不要重复进入同一条枝干。2.3 用广度优先搜索求解最短步骤的可行性分析为什么我修这份代码时选择把原来的递归DFS替换成BFS两个原因。第一BFS天然保证第一次到达目标状态的路径就是最短路径。对于“最少倒几次”这类问题来说这个性质至关重要。原代码虽然也能输出解但由于DFS的遍历顺序受容器编号影响给出的解通常绕远路不是最优的。第二状态空间太小。216个状态每个状态扩展6步最多1296次转移用数组实现的队列完全吃得开。我们不需要优先队列不需要哈希表只需一个大小合理的int数组就够了。容量固定时甚至可以用x * 6 * 4 y * 4 z这种简单编码作为状态下标。到这里算法的轮廓就清楚了状态编码、BFS队列、前驱回溯。这就是修复后的代码骨架。3. 复古代码的实测翻车现场与Bug定位全过程3.1 第一次编译警告刷屏我不确定这份代码当初是在哪个年代的编译器上写的但放到现在的gcc上第一条命令就给了我一个下马威gcc -Wall -o 79_wine 79_wine.c输出大概是这样的warning: implicit declaration of function pd warning: control reaches end of non-void function warning: bz may be used uninitialized warning: comparison between signed and unsigned integer expressions其中“implicit declaration”是致命伤在C89标准里函数如果没声明就直接调用编译器会默认它返回int且参数类型任意。这意味着pd()实际传进来的参数可能被截断或错误解释运行时行为完全不可控。而“control reaches end of non-void function”说明有的函数可能连返回值都没有。鉴于编译还能出可执行文件我决定先不看警告直接跑一遍把行为记录下来。3.2 静态阅读揪出的“致命三连”我把代码整理成带行号的版本逐个函数读。在坚持看到第四十个函数的时候终于发现了三个足以让程序崩溃的逻辑Bug。这里我用简化代码描述保留原作者的风格Bug 1状态编码与数组大小不匹配原作者用一个一维数组标记访问状态状态编号这样算int get_index(int x, int y, int z) { return x * (C21) * (C31) y * (C31) z; }其中C2和C3是5升杯和3升杯的容量所以理论上状态编号最大值是8 * 6 * 4 5 * 4 3 192 20 3 215而作者的bz数组只声明了int bz[100];最大下标215访问进去直接越界。越界会改写相邻内存里的其他变量比如它可能把某个全局变量改写掉造成完全无法解释的“灵异现象”。Bug 2倒酒量计算逻辑错误在实现“从i倒到j”时原代码大概是这样if (bucket[i] 0 bucket[j] max[j]) { if (bucket[i] max[j] - bucket[j]) { bucket[i] - bucket[j]; // 错误 bucket[j] max[j]; } else { bucket[j] bucket[i]; bucket[i] 0; } }这个分支里bucket[i] - bucket[j]把“从i倒出的量”错误地等于了“j当前已有的量”而实际上应该等于“j的剩余容量”。举个例子8升瓶有85升杯有38升瓶往5升杯倒剩余容量是2应该倒2但代码算成倒3于是得到bucket[i]5, bucket[j]5总量8变成10——凭空多出2升酒。这已经不是路径问题而是守恒律被打破了。Bug 3递归入口不标记状态原搜索函数在进入状态时没有立即将当前状态标记为已访问只在回溯时做某种标记导致递归状态图里出现环。前面已经解释过这会形成无限递归。这三个Bug单独拿出来都很“经典”它们同时出现在一份200行的代码里恰好说明一个问题写C语言时内存边界和搜索状态是最容易翻车的两座大山。3.3 通过加日志复现死循环与越界静态分析只能定位推断要对读者负责我还是要复现一遍。我没有用复杂的调试器而是用最土的办法在递归入口处打印当前状态和递归深度。结果运行到第几步时输出开始重复depth3 state(8,0,0) depth4 state(3,5,0) depth5 state(8,0,0) depth6 state(3,5,0)这就是典型的环形递归也能解释为什么程序不报错但永远跑不完。然后我在get_index后用类似assert(idx0 idx215)的方式去检查程序跑了一阵就直接弹“Assertion failed”连带打印出过界的下标值比如220、230。一旦出现越界程序修改了bz数组内存之外的全局变量之后的一切输出都不可信。3.4 每一步修复对应的原理修复的方案其实都不复杂重点是理解背后的原理。把bz数组大小改成(V01)*(V11)*(V21)避免一切越界。倒酒量统一计算为int pour min(bucket[i], max[j] - bucket[j]);这保证总量守恒。在BFS中状态扩展前先检查visited[index]为0才入队并标记为1。顺序也很重要先修数组越界再修倒酒逻辑最后换BFS。如果顺序反过来可能刚修好BFS又被越界干扰你会以为BFS实现错了白白浪费时间。这种排查顺序本身就是老手和新手的区别先解决所有内存安全类问题再谈算法正确性。4. 修复后的现代C实现与关键差异对照4.1 数据结构从零散全局数组到结构体旧代码最大的结构问题是所有状态都用全局变量bucket[3]和pre[1000]来传递函数之间通过直接改全局来通信。这种代码一旦函数调用深了状态会被改得面目全非。我的修复版里用一个结构体表示状态节点typedef struct { int cur[3]; int parent; int from; int to; } State;cur保存该状态下的三个容器的酒量parent记录队列中父节点的下标from和to记录从根状态到当前状态这最后一步操作是从哪个容器倒到哪个容器。这样只要从终止节点倒着遍历parent链就能还原完整操作序列。4.2 核心逻辑不变量、状态哈希、队列实现状态编码沿用之前的一维下标方法。假设三个容器容量为cap[0]、cap[1]、cap[2]当前酒量为x,y,z则下标为int index x * (cap[1]1) * (cap[2]1) y * (cap[2]1) z;因为x的取值从0到cap[0]有cap[0]1种但严格来说x的取值还受到总量约束不过用完整区间分配数组也没有浪费多少内存。BFS队列用最简单的数组实现State queue[MAX_STATES]; int head 0, tail 0; queue[tail] initialState; visited[stateIndex] 1;每次从head取一个状态遍历6种倒法对每个合法的新状态计算index如果没访问就填入队列并标记。当取出的状态中任意cur[i] target时就找到了解。这里要特别注意判断目标的时间点应该在“出队时”还是在“入队前”对于最短路径两种写法都能保证正确但如果你在入队前判断需要同时记录parent为新节点的下标稍微绕一点。我习惯在出队时判断代码更清晰。4.3 完整代码与运行演示我贴出修复后的完整代码总共不到170行。可以直接保存为poisson_wine.c用gcc -Wall -o poisson_wine poisson_wine.c编译。#include stdio.h #include string.h #define MAX_STATES 512 typedef struct { int cur[3]; int parent; int from; int to; } State; int cap[3]; int totalVolume 0; /* 状态编码一维下标 */ int getIndex(int x, int y, int z) { return x * (cap[1] 1) * (cap[2] 1) y * (cap[2] 1) z; } /* 从状态s倒第i容器到第j容器结果写入next */ int pour(const State *s, int i, int j, State *next) { if (i j) { return 0; } if (s-cur[i] 0 || s-cur[j] cap[j]) { return 0; } int space cap[j] - s-cur[j]; int pourAmount (s-cur[i] space) ? s-cur[i] : space; next-cur[0] s-cur[0]; next-cur[1] s-cur[1]; next-cur[2] s-cur[2]; next-cur[i] - pourAmount; next-cur[j] pourAmount; next-parent -1; next-from i; next-to j; return 1; } int main(void) { int target; printf(input target volume: ); if (scanf(%d, target) ! 1) { printf(invalid input\n); return 1; } /* 示例三个容器容量 8 5 3初始为 8 0 0 */ cap[0] 8; cap[1] 5; cap[2] 3; totalVolume cap[0]; /* 初始化状态空间及访问标记 */ int stateSize (cap[0] 1) * (cap[1] 1) * (cap[2] 1); static char visited[MAX_STATES]; static State queue[MAX_STATES]; memset(visited, 0, sizeof(char) * stateSize); State initState; initState.cur[0] totalVolume; initState.cur[1] 0; initState.cur[2] 0; initState.parent -1; initState.from -1; initState.to -1; int head 0, tail 0; queue[tail] initState; visited[getIndex(initState.cur[0], initState.cur[1], initState.cur[2])] 1; int answerIndex -1; while (head tail) { State curState queue[head]; if (curState.cur[0] target || curState.cur[1] target || curState.cur[2] target) { answerIndex head - 1; break; } State next; for (int i 0; i 3; i) { for (int j 0; j 3; j) { if (i j) { continue; } if (pour(curState, i, j, next)) { int idx getIndex(next.cur[0], next.cur[1], next.cur[2]); if (!visited[idx]) { visited[idx] 1; next.parent head - 1; if (tail MAX_STATES) { printf(queue overflow\n); return 1; } queue[tail] next; } } } } } if (answerIndex -1) { printf(no solution\n); return 0; } /* 反向回溯路径 */ int path[MAX_STATES]; int cnt 0; int p answerIndex; while (p ! -1) { path[cnt] p; p queue[p].parent; } printf(found with %zu steps:\n, (size_t)(cnt - 1)); for (int i cnt - 1; i 0; i--) { int idx path[i]; if (queue[idx].from -1) { printf(start: (%d, %d, %d)\n, queue[idx].cur[0], queue[idx].cur[1], queue[idx].cur[2]); } else { printf(pour %d - %d: (%d, %d, %d)\n, queue[idx].from, queue[idx].to, queue[idx].cur[0], queue[idx].cur[1], queue[idx].cur[2]); } } return 0; }编译运行输入4输出如下input target volume: 4 found with 7 steps: start: (8, 0, 0) pour 0 - 1: (3, 5, 0) pour 1 - 2: (3, 2, 3) pour 2 - 0: (6, 2, 0) pour 1 - 2: (6, 0, 2) pour 0 - 1: (1, 5, 2) pour 1 - 2: (1, 4, 3) pour 2 - 0: (4, 4, 0)用语言描述就是8升瓶倒满5升瓶5升瓶倒满3升瓶3升瓶倒回8升瓶5升瓶剩下的2升倒入3升瓶8升瓶倒满5升瓶5升瓶倒1升进3升瓶此时3升瓶满2升还能装1升5升瓶剩4升最后3升瓶倒回8升瓶8升瓶也是4升。完美得到两个4升。4.4 和旧版对比不只是能跑而是能讲清楚修复后代码和旧代码的差异我用一张表列清楚对比维度旧版79_wine.c修复版状态存储全局数组局部变量混合结构体队列自带父子关系状态判重数组未指定大小且入队时机错误入队前判重数组按状态全集分配倒酒逻辑部分分支破坏了总量守恒统一取min(源剩余, 目标剩余空间)搜索方式递归DFS回溯混乱迭代BFS天然闭环路径还原没有记录操作步骤每个节点记录from/to/parent输入校验无检查scanf返回值处理非法输入最让我感慨的是旧版其实已经迈出了“用状态空间解题”这一步但因为没有先算清楚状态数把一个本该很清晰的问题写成了玄学。修复版没有引入任何高级库全部靠C语言基本功这就是当初老代码最值得保留的部分。5. 维护旧C语言代码的一些实战心得5.1 面对漫天全局变量先画状态图再动手修代码最忌讳的是上来就改。拿这份79泊松分酒为例如果我一进场就盯着某个全局变量瞎猜可能三天都找不出问题。我的流程是先用纸画一下状态转移图标出哪些状态是目标状态哪些操作会形成回路。状态图一画出来死循环的原因就变成了“图上有个环”而不是“递归有问题”。这个过程放在职业场景里也一样。你接手别人留下的C语言项目无论对方写得多烂第一步永远是“理解业务状态”第二步才是“看代码实现”。没有状态图你连“Bug到底影响了哪条路径”都说不清。5.2 调试旧代码的“土办法”比断点更管用现代IDE里的调试器确实强大但处理这种老代码时我反而推荐用printf加状态编号的方式。原因很实在旧代码通常干了大量“偷偷改全局变量”的事断点只能看到当前函数却很难看到“是谁在很久之前把这个变量改坏了”。打印日志可以记录完整轨迹一眼看出状态环。当然现代工具也不是不能用。比如在VS Code里配好C语言环境然后设置条件断点只在某个特定状态出现时中断也很高效。但前提是你得先知道“某个特定状态”长什么样。先用printf跑一轮把所有状态序列导出来再决定在哪里打断点这是成本最低的路线。5.3 关于“79”的最后一点猜想修完这份代码我又看了一眼文件名里的“79”。它既可能是教材题号也可能是某个BBS系统分配给上传文件的序号还可能是“1979年的代码”——虽然这个可能性很低因为70年代的C代码大概率不会用//风格注释。其实是什么不重要重要的是它给我留了一个悬念让我愿意花一个晚上去研究一份几乎被遗忘的程序。类似这样的古董代码很多老程序员手里都有一堆。它们不一定漂亮不一定正确但往往蕴藏着一个完整的思考过程。比起去看十篇“C语言必背100代码”倒不如翻出一份老代码亲手把它从“能跑但不对”修到“又对又好看”。这中间踩的坑、悟的道理才是真正的经验积累。如果你身边也有这样的旧文件别急着删试着修修看说不定也能写出一篇比我这篇更有意思的修复记录。