1. 项目概述从一道经典算法题看编程思维“百钱买百鸡”这道题但凡学过一点编程的朋友估计都绕不过去。我第一次接触它还是在大学C语言课上当时觉得这不就是个三重循环暴力穷举吗有什么难的。但真正在项目里摸爬滚打十几年后再回头看这道题发现它简直是一个完美的“麻雀”五脏俱全能解剖出从问题抽象、算法设计、代码优化到工程思维的完整链条。它绝不仅仅是让你写出一个能跑的程序而是逼着你去思考如何让计算机更“聪明”地解决问题。简单来说题目是这样的公鸡5文钱一只母鸡3文钱一只小鸡1文钱三只。现在要用100文钱正好买100只鸡问公鸡、母鸡、小鸡各有多少只题目本身源自中国古代数学著作《张邱建算经》是一个典型的不定方程整数解问题。用C来实现它就像木匠用刨子、程序员用键盘一样自然。这道题之所以经典是因为它门槛低但上限高。新手可以借此理解循环和条件判断进阶者能探讨时间复杂度和算法优化老手则能从中品出抽象建模和边界处理的工程味道。无论你是刚配置好VS Code的C环境还是在啃“C八股文”准备面试亦或是想找个练手小项目它都是一个绝佳的起点。2. 问题建模与数学分析把生活问题翻译成代码逻辑动手写代码之前我们得先当好“翻译官”把文绉绉的中文题目翻译成冷冰冰的数学方程最后再转成严丝合缝的代码逻辑。这一步直接决定了后续代码是简洁优雅还是臃肿不堪。2.1 建立数学模型首先我们定义三个变量设公鸡数量为x只设母鸡数量为y只设小鸡数量为z只根据题意我们可以列出两个方程数量方程x y z 100总共100只鸡价格方程5x 3y z/3 100总共100文钱这里有一个关键点小鸡是“1文钱三只”所以z只小鸡的总价是z/3文钱。同时鸡的数量必须是整数且公鸡、母鸡、小鸡的数量都不能为负数。由此我们得到了一个包含三个未知数但只有两个方程的不定方程组。从数学上讲它的解可能不唯一甚至可能无解。我们的任务就是找出所有满足条件的非负整数解(x, y, z)。2.2 确定变量的取值范围解空间分析这是优化算法的关键。如果无脑穷举假设每种鸡都可能从0到100只那循环次数是101 * 101 * 101超过一百万次。但利用约束条件我们可以大幅缩小搜索范围。1. 公鸡x的范围一只公鸡5文钱100文钱全买公鸡最多买100 / 5 20只。所以x的取值范围是[0, 20]。2. 母鸡y的范围一只母鸡3文钱100文钱全买母鸡最多买100 / 3只向下取整是33只。所以y的取值范围是[0, 33]。3. 小鸡z的范围小鸡的只数z可以通过z 100 - x - y直接计算出来不需要单独循环。但要注意一个隐含条件因为小鸡是3只一起卖所以z必须能被3整除 (z % 3 0)否则总价会出现小数文钱不符合现实。4. 利用价格方程进一步剪枝我们还可以从价格方程5x 3y z/3 100推导出另一个关系。将z 100 - x - y代入价格方程5x 3y (100 - x - y)/3 100两边乘以3消去分母15x 9y 100 - x - y 300化简得14x 8y 200进一步化简7x 4y 100这个方程比原方程更简洁只涉及x和y。我们可以直接用它来判断或者用它来推导y关于x的表达式y (100 - 7x) / 4。这要求(100 - 7x)必须能被4整除且结果y为非负整数。这比单纯循环判断更高效。注意在实际编程教学中我通常不会一开始就抛出化简后的方程。我会引导学生先写出最直观的三重循环运行成功后再带领他们一步步分析、优化。这个过程本身比直接给出最优解更有价值它模拟了真实的代码重构和性能优化流程。3. 基础实现从暴力穷举开始理解了数学模型我们就可以开始用C实现了。我们从最直观、最易理解的版本开始。3.1 三重循环暴力破解法这是最直接的思路遍历所有可能的公鸡、母鸡、小鸡数量组合检查是否同时满足总数为100、总价为100、小鸡数是3的倍数这三个条件。#include iostream using namespace std; int main() { int cock, hen, chick; // 对应公鸡、母鸡、小鸡 int solutionCount 0; // 记录解的数量 cout 暴力穷举法求解百钱百鸡问题 endl; cout 公鸡\t母鸡\t小鸡 endl; cout --------------------- endl; for (cock 0; cock 20; cock) { // 公鸡最多20只 for (hen 0; hen 33; hen) { // 母鸡最多33只 for (chick 0; chick 100; chick 3) { // 小鸡数量是3的倍数 // 检查总数和总价 if ((cock hen chick 100) (5 * cock 3 * hen chick / 3 100)) { cout cock \t hen \t chick endl; solutionCount; } } } } cout --------------------- endl; cout 共找到 solutionCount 组解。 endl; return 0; }代码解析与心得变量命名我使用了cock,hen,chick而不是简单的x, y, z。在小型算法题中这或许有点“过度设计”但它培养了一个好习惯代码即文档。清晰的变量名能让阅读者包括未来的你自己立刻明白其含义无需注释。循环边界虽然小鸡理论上可以到100只但我在循环里直接让chick以3为步长递增 (chick 3)。这是一个小小的优化直接避免了在循环体内用if (chick % 3 0)来判断将判断次数从O(n)降到了O(1)。输出格式化使用了\t制表符来对齐输出让结果看起来更整洁。这是提升程序用户体验的一个细节。这个版本的时间复杂度是 O(20 * 33 * 34) ≈ O(22440)虽然对于现代计算机来说瞬间完成但作为一个教学示例我们可以做得更好。3.2 优化为双重循环既然小鸡数量z可以通过z 100 - x - y计算得出我们完全可以省去最内层循环。#include iostream using namespace std; int main() { int cock, hen, chick; int solutionCount 0; cout 双重循环优化法求解 endl; cout 公鸡\t母鸡\t小鸡 endl; cout --------------------- endl; for (cock 0; cock 20; cock) { for (hen 0; hen 33; hen) { chick 100 - cock - hen; // 直接计算小鸡数量 // 条件小鸡数非负、是3的倍数、总价满足 if (chick 0 chick % 3 0 (5 * cock 3 * hen chick / 3 100)) { cout cock \t hen \t chick endl; solutionCount; } } } cout --------------------- endl; cout 共找到 solutionCount 组解。 endl; return 0; }优化点分析循环次数从约2.2万次 (20*33*34) 降到了约700次 (21*34)性能提升超过30倍。条件判断将小鸡数量非负 (chick 0) 作为第一个判断条件。这是一个有效的“短路”优化。因为当cock和hen很多时chick可能为负数先判断它就能提前结束后续无用的取模和乘法运算。可读性代码逻辑更清晰直接体现了“用总数约束减少一个维度”的思想。实操心得在写循环时尤其是嵌套循环要养成分析循环边界和提前终止条件的习惯。即使在这个简单例子里chick 0这个判断也过滤掉了将近一半的无用组合。在实际业务代码中这种细微的优化累积起来效果惊人。4. 高级优化与算法思维逼近最优解如果还想再压榨一下性能或者应对更复杂的约束条件我们可以运用更深入的数学分析。4.1 利用方程消元实现单层循环还记得我们推导出的关系式7x 4y 100吗我们可以用它来直接求解。#include iostream using namespace std; int main() { int cock, hen, chick; int solutionCount 0; cout 单层循环数学消元法求解 endl; cout 公鸡\t母鸡\t小鸡 endl; cout --------------------- endl; for (cock 0; cock 20; cock) { // 根据 7x 4y 100 推导出 y (100 - 7*cock) / 4 int remainder 100 - 7 * cock; // 首先余数必须非负 if (remainder 0) break; // 因为cock递增一旦余数为负后面都负可提前结束循环 // 其次余数必须能被4整除 if (remainder % 4 ! 0) continue; // 不能整除跳过本次循环 hen remainder / 4; // 检查母鸡数量是否在合理范围内 if (hen 0 || hen 33) continue; chick 100 - cock - hen; // 检查小鸡数量是否非负且是3的倍数理论上由方程保证但双重检查更稳健 if (chick 0 chick % 3 0) { cout cock \t hen \t chick endl; solutionCount; } } cout --------------------- endl; cout 共找到 solutionCount 组解。 endl; return 0; }算法精髓降维打击通过数学变换将三重循环问题降为单重循环问题。循环次数从700次进一步降到最多21次。提前退出if (remainder 0) break;这一句是点睛之笔。当cock增加到一定数量7*cock超过100时remainder为负意味着后续所有更大的cock都不可能产生解。直接break跳出循环避免了无意义的迭代。健壮性检查尽管从数学上推导求出的hen和chick应该自然满足范围和小鸡倍数条件但代码中依然保留了范围检查 (hen 33) 和条件检查 (chick % 3 0)。这是一个好的编程实践防止因推导疏忽或未来需求变更比如价格变化导致的隐藏错误。4.2 扩展思考如果价格或总数变化怎么办我们之前的代码都硬编码了价格531/3和总数100。一个更工程化的写法是将这些作为变量或常量。#include iostream using namespace std; // 使用常量定义方便修改和阅读 const int TOTAL_MONEY 100; const int TOTAL_CHICKENS 100; const int PRICE_COCK 5; const int PRICE_HEN 3; const int PRICE_CHICK_PER_THREE 1; // 三只小鸡的价格 const int CHICK_GROUP 3; // 小鸡的售卖单位 void solveChickenProblem(int money, int chickens, int priceCock, int priceHen, int priceChickGroup, int chickGroupSize) { cout 参数化求解钱 money 鸡 chickens 公鸡价 priceCock 母鸡价 priceHen 每 chickGroupSize 只小鸡价 priceChickGroup endl; cout 公鸡\t母鸡\t小鸡 endl; cout --------------------- endl; int count 0; int maxCock money / priceCock; for (int cock 0; cock maxCock; cock) { int maxHen (money - priceCock * cock) / priceHen; for (int hen 0; hen maxHen; hen) { int moneyLeft money - priceCock * cock - priceHen * hen; // 剩下的钱必须能买整数“组”小鸡 if (moneyLeft % priceChickGroup ! 0) continue; int chickGroups moneyLeft / priceChickGroup; // 买了多少“组”小鸡 int chick chickGroups * chickGroupSize; // 小鸡总数 if (cock hen chick chickens) { cout cock \t hen \t chick endl; count; } } } if (count 0) { cout 无解 endl; } else { cout 共找到 count 组解。 endl; } } int main() { // 求解原问题 solveChickenProblem(TOTAL_MONEY, TOTAL_CHICKENS, PRICE_COCK, PRICE_HEN, PRICE_CHICK_PER_THREE, CHICK_GROUP); cout \n--- 测试其他参数 ---\n; // 例如120文钱买100只鸡 solveChickenProblem(120, 100, 5, 3, 1, 3); return 0; }工程化提升参数化将核心逻辑封装成函数所有约束条件都作为参数传入。这使得代码复用性极高可以轻松求解“百钱买百鸡”的各种变体。动态计算边界maxCock money / priceCock和maxHen (money - priceCock * cock) / priceHen根据剩余资金动态计算上限比写死的20和33更通用。清晰的常量定义使用const常量而非魔法数字如53100提高了代码的可读性和可维护性。如果需要调整价格测试只需修改常量定义处。5. 代码实现中的常见“坑”与调试技巧即使是这样简单的程序新手甚至有一定经验的开发者也容易踩坑。下面我结合常见问题分享一些调试和避坑经验。5.1 整数除法与取模的陷阱这是本题最容易出错的地方。小鸡的价格是“1文钱3只”在计算总价时必须是chick / 3而不是chick * 1 / 3或其他。更关键的是在C中两个整数相除结果仍是整数会直接舍弃小数部分。// 错误示例1错误的总价计算 int chick 99; int price 5*cock 3*hen chick * 1 / 3; // 错chick*1/3 等于 (99*1)/3 33但实际价格是99/333文这里巧合对了但逻辑不对。 // 正确应该是 chick / 3 // 错误示例2先判断倍数再计算 if (5*cock 3*hen chick/3 100) { // 如果chick不是3的倍数chick/3已经丢失了精度 // ... } // 应该先判断 chick % 3 0 if (chick % 3 0 5*cock 3*hen chick/3 100) { // ... }避坑指南在处理涉及整数除法且需要精确等值比较时务必先进行取模判断确保能整除后再进行除法运算。或者更推荐的做法是像我们参数化版本那样将所有价格转换为同一单位比如都以“文”为单位通过乘法来避免除法即检查5*cock 3*hen chick/3 100等价于检查15*cock 9*hen chick 300两边乘以3。后者完全避免了整数除法。5.2 循环边界条件错误另一个常见错误是循环边界设得太大或太小。// 错误小鸡循环边界错误 for (chick 0; chick 100; chick) { // 步长为1循环100次但其中只有约1/3的情况chick是3的倍数 if (chick % 3 0 ...) // 内部判断增加了开销 } // 优化for (chick 0; chick 100; chick 3) // 错误公鸡边界计算错误 int maxCock 100 / 5; // 正确是20 for (int cock 1; cock maxCock; cock) { // 错误cock20的情况被排除可能漏解。 // 应该是 cock maxCock调试技巧对于这类边界错误一个有效的方法是打印边界值。在循环开始前把计算出的maxCock,maxHen打印出来看是否符合预期。对于可能漏掉边界的情况可以用一个简单的测试用例比如钱只够买一种鸡看程序是否能找出那个解。5.3 多重条件判断的顺序与逻辑条件判断的顺序会影响程序效率。// 效率较低的判断顺序 if ((cock hen chick 100) (chick % 3 0) (5*cock 3*hen chick/3 100)) { // ... } // 效率较高的判断顺序 if (chick % 3 0) { // 先判断代价低的条件 if (cock hen chick 100) { // 再判断中间条件 if (5*cock 3*hen chick/3 100) { // 最后判断计算最复杂的条件 // ... } } } // 或者使用短路与()它会从左到右计算一旦为假就停止。 if (chick % 3 0 cock hen chick 100 5*cock 3*hen chick/3 100) { // 注意这里把计算最简单的放前面 }经验之谈在组合条件判断中将最可能为假或计算成本最低的条件放在前面。短路运算符||会提前终止计算这能有效提升性能尤其是在深层循环中。6. 从“百钱百鸡”延伸到更广泛的编程问题“百钱买百鸡”本质上是一类“约束满足问题”的简化版。掌握了它的解法你可以触类旁通解决许多类似问题。6.1 同类问题举一反三“换零钱”问题有1元、2元、5元纸币若干要凑出100元有多少种组合这几乎是同一类问题只是约束条件从“总数固定”变成了“总金额固定”。“方程整数解”问题例如求3x 5y 7z 100的所有正整数解。解法完全一样确定每个变量的范围然后循环穷举或优化。资源分配问题例如有CPU密集型、IO密集型、内存密集型三种任务在有限的CPU、IO、内存资源下如何分配任务数量使得总吞吐量最大这可以建模为在资源约束下求某个目标函数的最大值搜索解空间的方法与本题一脉相承。6.2 算法优化思想的进阶我们优化“百钱百鸡”的过程体现了经典的算法优化思想减少维度通过等式消去一个变量小鸡z。缩小搜索空间利用价格和数量约束大幅降低每个变量的循环上限。数学推导剪枝利用7x4y100和整除性质直接过滤掉大量无效组合甚至降为单层循环。这些思想在解决“背包问题”、“旅行商问题”等更复杂的组合优化问题时会以更高级的形式出现如动态规划、分支限界法、启发式搜索等。理解这个简单案例中的优化本质是通向理解复杂算法的阶梯。6.3 在C学习路径中的位置对于C学习者这个项目位于一个承上启下的位置之前你需要掌握基本的变量、数据类型、输入输出、条件判断和循环。本项目综合运用上述知识并引入“枚举”、“暴力搜索”、“优化”等算法雏形概念。之后你可以在此基础上学习函数封装如我们做的参数化函数学习如何设计函数接口。文件输入输出从控制台输入价格和总数或将结果输出到文件。简单计时使用chrono库比较不同算法实现的耗时直观感受优化效果。面向对象雏形可以定义一个ChickenProblemSolver类将问题参数和求解方法封装在一起。我个人在带新人时常把这道题作为第一个小项目。它结果直观能快速获得成就感又留有足够的优化空间供探索。写完能跑通的代码只是第一步去思考“还有没有更快的方法”“如果条件变了怎么办”“我的代码足够清晰健壮吗”这才是通向资深工程师的道路。下次当你再看到类似的“XX钱买XX鸡”或者更复杂的约束问题希望你能会心一笑因为你知道钥匙已经在手里了。