1. 项目概述从一道经典算法题说起“百钱百鸡”问题相信很多C初学者甚至是有一定经验的开发者都曾在算法练习或面试准备中遇到过它。题目本身并不复杂公鸡5文钱一只母鸡3文钱一只小鸡1文钱三只用100文钱买100只鸡问公鸡、母鸡、小鸡各多少只这本质上是一个整数解的不定方程问题。乍一看这似乎只是一个简单的数学应用题用三重循环暴力枚举就能解决。但如果你真的只停留在“写出一个能跑通的程序”这个层面那就错过了这道题背后蕴藏的、对于C程序员而言极其宝贵的训练价值。在我看来“百钱百鸡”是一个绝佳的算法思维与工程实践的结合点。它像一面镜子能清晰地照出一个程序员思考问题的层次是仅仅满足于功能实现还是会去考虑效率、代码的优雅性、可扩展性以及背后的数学原理对于新手它是理解循环、条件判断和基础算法如枚举法的入门砖对于进阶者它是探讨算法优化如减少循环层数、利用数学关系剪枝、理解时间复杂度、乃至练习编写测试用例和性能分析的练手场。今天我就以一名老码农的视角带大家重新解构这个经典问题不仅给出答案更要深挖每一步选择背后的“为什么”分享一些在教科书和简单教程里不会提到的实操心得和避坑技巧。2. 问题建模与核心思路拆解2.1 数学方程建立首先我们需要将自然语言描述的问题转化为严谨的数学模型。这是所有编程解决问题的第一步也是最关键的一步模型建得准代码才能写得对。设公鸡数量为x母鸡数量为y小鸡数量为z。根据题意我们可以列出两个方程数量方程x y z 100总数为100只价格方程5*x 3*y z/3 100总钱数为100文这里有一个细节需要注意小鸡是“1文钱三只”因此小鸡的单价是1/3文。在程序中我们必须确保z是3的倍数否则z/3会出现非整数结果这与现实情况不符。同时x,y,z都是非负整数。所以我们的编程目标就变成了寻找所有满足上述两个方程且x,y,z为非负整数z能被3整除的三元组(x, y, z)。2.2 算法策略选择从暴力枚举到优化剪枝最直观的解法就是三重循环暴力枚举。让x从0循环到100y从0循环到100z从0循环到100检查每一组组合是否满足条件。这种方法的代码最简单但效率也最低循环次数是101 * 101 * 101 ≈ 1,030,000次。对于现代计算机虽然瞬间完成但作为一种思维训练我们不能满足于此。优化思路一利用总数约束减少循环层数由方程x y z 100我们可以得到z 100 - x - y。这样一来我们只需要两层循环枚举x和yz可以通过计算直接得到。这立即将循环次数从百万级降低到了万级101 * 101 ≈ 10,000次。优化思路二利用价格约束确定循环范围公鸡5文一只100文全买公鸡也只能买20只所以x的范围是[0, 20]。 母鸡3文一只100文全买母鸡最多买33只因为100/333.33取整所以y的范围是[0, 33]。 确定了x和y后z必须等于100 - x - y且必须非负。这进一步缩小了搜索空间。优化思路三利用整数与倍数约束提前判断在计算出z后我们不仅要检查z 0还必须检查z % 3 0确保小鸡数量是3的倍数。5*x 3*y z/3 100确保总价正好100文。注意这里有一个初学者常犯的错误。在C中如果z是整数z/3是整数除法会直接截断小数部分。例如z5时z/3的结果是1这显然不符合“5只小鸡价值5/3文”的数学事实。因此在判断总价时更严谨的做法是避免使用整数除法或者将方程变形。我们可以将价格方程两边乘以3来消除分母15*x 9*y z 300。这样我们只需要检查15*x 9*y z 300即可完全避免了除法运算和类型转换的困扰。这是处理这类涉及分数问题的一个经典技巧。基于以上分析我们将采用优化后的双重循环枚举法作为核心实现方案。循环变量x从0到20y从0到33计算z然后判断z的非负性、是否为3的倍数并验证变形后的总价方程。3. 核心代码实现与逐行解析接下来我们动手编写C代码。我会使用标准C11及以上版本并尽量保持代码的清晰和可读性。3.1 基础版本实现我们先给出一个结构清晰、注释完整的基础版本。#include iostream using namespace std; int main() { int cock, hen, chick; // 分别代表公鸡、母鸡、小鸡的数量 int solutionCount 0; // 记录解的数量 cout 百钱百鸡问题所有解 endl; cout 公鸡\t母鸡\t小鸡 endl; // 制表符对齐输出 // 外层循环枚举公鸡可能数量 (0 到 20) for (cock 0; cock 20; cock) { // 内层循环枚举母鸡可能数量 (0 到 33) for (hen 0; hen 33; hen) { // 根据总数约束计算小鸡数量 chick 100 - cock - hen; // 条件判断 // 1. 小鸡数量不能为负数 // 2. 小鸡数量必须是3的倍数因为1文钱3只 // 3. 验证总价方程已变形为整数形式15*cock 9*hen chick 300 if (chick 0 chick % 3 0 (15 * cock 9 * hen chick 300)) { // 找到一组解输出并计数 cout cock \t hen \t chick endl; solutionCount; } } } cout 总共找到 solutionCount 组解。 endl; return 0; }代码解析与关键点变量命名使用了cock,hen,chick这样清晰的英文单词比简单的x, y, z更具可读性。在实际项目中良好的变量名是减少后期维护成本的关键。循环范围cock循环上限是20hen是33这是由价格约束推导出的是重要的优化。核心判断逻辑if条件中的三个判断是核心。chick 0确保小鸡数量非负。虽然在这个循环范围内cockhen最大为53chick最小为47肯定非负但保留这个判断是一个好习惯使逻辑自洽。chick % 3 0确保小鸡数量是3的倍数满足单价约束。15*cock 9*hen chick 300这是变形后的总价方程。避免了chick/3的整数除法问题直接进行整数比较更快更准确。输出格式化使用\t制表符对齐输出使结果更美观。运行这段代码你会得到四组解公鸡 母鸡 小鸡 0 25 75 4 18 78 8 11 81 12 4 843.2 进阶优化与代码重构基础版本已经高效且正确。但我们还可以从工程化和可扩展性角度进行优化。版本二使用函数封装提高可复用性将求解逻辑封装成一个函数使主函数更简洁也方便未来进行单元测试或集成到其他项目中。#include iostream #include vector #include tuple // 用于返回多个值这里用结构体替代更清晰 using namespace std; // 定义一个结构体来存储一组解 struct Solution { int cocks; int hens; int chicks; // 可以添加一个构造函数方便初始化 Solution(int c, int h, int ch) : cocks(c), hens(h), chicks(ch) {} }; // 求解函数返回所有解的向量 vectorSolution solveHundredChickens() { vectorSolution solutions; const int TOTAL_MONEY 100; const int TOTAL_BIRDS 100; const int COCK_PRICE 5; const int HEN_PRICE 3; // 小鸡单价为 1/3在方程变形中处理 int maxCocks TOTAL_MONEY / COCK_PRICE; // 20 int maxHens TOTAL_MONEY / HEN_PRICE; // 33 for (int c 0; c maxCocks; c) { for (int h 0; h maxHens; h) { int ch TOTAL_BIRDS - c - h; // 小鸡数量 if (ch 0 ch % 3 0) { // 使用变形后的整数方程5*3*c 3*3*h ch 100*3 if (COCK_PRICE * 3 * c HEN_PRICE * 3 * h ch TOTAL_MONEY * 3) { solutions.emplace_back(c, h, ch); // 使用emplace_back原地构造效率更高 } } } } return solutions; } int main() { auto results solveHundredChickens(); cout 百钱百鸡问题所有解 endl; cout 序号\t公鸡\t母鸡\t小鸡 endl; int count 1; for (const auto sol : results) { cout count .\t sol.cocks \t sol.hens \t sol.chicks endl; } cout 总共找到 results.size() 组解。 endl; // 附加分析计算每种方案的花费分布可选 cout \n各方案花费分析 endl; for (const auto sol : results) { int costCocks 5 * sol.cocks; int costHens 3 * sol.hens; int costChicks sol.chicks / 3; // 此处除法安全因为chicks是3的倍数 cout 方案 (sol - results[0] 1) : 公鸡 costCocks 文母鸡 costHens 文小鸡 costChicks 文 endl; } return 0; }这个版本的改进点函数化solveHundredChickens函数职责单一只负责计算并返回解。这符合软件设计的“单一职责原则”。使用常量将总钱数、总数、价格等定义为常量提高了代码的可读性和可维护性。如果需要改变题目参数比如“百钱两百鸡”只需修改常量即可。使用vector和struct用vectorSolution存储所有解比直接在循环中输出更灵活。Solution结构体使数据成组意义明确。使用emplace_back在向vector添加元素时emplace_back可以直接在容器内存中构造对象避免了push_back先创建临时对象再拷贝或移动的开销对于自定义类型效率更高。附加功能主函数中增加了对解集的分析计算了每种方案的钱数分布展示了如何处理结果数据。实操心得在写这种算法小练习时有意识地采用良好的工程实践如定义常量、使用结构体、编写纯函数虽然看起来“杀鸡用牛刀”但对于培养扎实的编码习惯至关重要。当你面对大型项目时这些习惯会成为你的肌肉记忆。4. 算法深度优化探索虽然双重循环已经足够快但我们还可以从数学角度进一步优化甚至减少到一重循环。这不仅是性能的极致追求更是算法思维的锻炼。4.1 利用方程消元实现单层循环我们有两个方程 (1)x y z 100(2)5x 3y z/3 100 变形为15x 9y z 300将方程(1)的z 100 - x - y代入变形后的方程(2)15x 9y (100 - x - y) 300化简得14x 8y 200两边同时除以27x 4y 100现在我们得到了一个关于x和y的二元一次方程。我们可以用y来表示x4y 100 - 7xy (100 - 7x) / 4由于y必须是整数所以(100 - 7x)必须能被4整除。同时y也必须是非负整数所以(100 - 7x) / 4 0这给出了x的上限。另外由y 33也能约束x。单层循环实现#include iostream using namespace std; int main() { int x, y, z; cout 百钱百鸡问题所有解单循环优化 endl; cout 公鸡\t母鸡\t小鸡 endl; // 循环公鸡数量 x // 由 y (100 - 7x)/4 0 得 x 100/7 ≈ 14.28所以 x 14 // 同时由原始价格约束x 最大为20这里取更严格的14 for (x 0; x 14; x) { // 计算 (100 - 7x) 的值 int remainder 100 - 7 * x; // 检查 remainder 是否能被4整除并且非负由循环条件已保证 if (remainder 0 remainder % 4 0) { y remainder / 4; // 计算母鸡数量 z 100 - x - y; // 计算小鸡数量 // 由于推导自原方程z自动满足非负和3的倍数吗需要验证。 // 验证小鸡数量非负且为3的倍数 if (z 0 z % 3 0) { // 可以再加一道价格验证虽然理论上应成立 if (5*x 3*y z/3 100) { cout x \t y \t z endl; } } } } return 0; }这个版本的循环次数从最多21*34714次双重循环优化版降低到了最多15次。这是一个巨大的性能提升尤其是在问题规模扩大时这种数学优化的优势将更加明显。避坑技巧在进行了数学变换后一定要验证结果是否仍然满足原问题的所有约束。例如我们从7x4y100和xyz100推导出解但必须回头验证z是否真的是3的倍数以及总价是否精确为100文。这是因为在推导过程中我们可能无意中引入或忽略了某些整数约束。加上验证步骤是保证程序健壮性的好习惯。4.2 性能对比与时间复杂度分析我们来量化一下不同算法的时间复杂度三重暴力枚举O(n³)n约等于100执行约100万次循环。双重循环优化O(n²)n约等于20和33执行最多714次循环。单层数学优化O(n)n约等于14执行最多15次循环。在本题数据规模下三种方法看起来都“瞬间完成”。但设想一下如果钱数和鸡数从100变成10000万钱万鸡那么算法效率的差异就会天差地别。O(n³)的算法将变得完全不可行而O(n)的算法依然轻松。这就是算法优化的意义所在——它培养的是一种应对规模增长时的 scalability可扩展性思维。5. 常见问题、调试技巧与扩展思考5.1 新手常犯错误实录整数除法陷阱// 错误写法 if (5*x 3*y z/3 100) { ... } // 当z不是3的倍数时z/3会被截断 // 正确写法使用变形后的整数方程 if (15*x 9*y z 300) { ... } // 或者确保在判断前z已是3的倍数 if (z % 3 0 5*x 3*y z/3 100) { ... }循环范围过大for (int x 0; x 100; x) // 低效公鸡不可能超过20只没有利用价格约束来缩小搜索范围导致大量无用的循环。忽略非负约束z 100 - x - y; // 如果不检查 z 0当 xy 100 时z为负数但仍可能满足后续的取模和价格判断因为负数%3结果可能为0或负等式也可能巧合成立产生错误解。输出格式混乱直接连续输出x, y, z而没有分隔符或换行导致结果挤在一起难以阅读。5.2 调试技巧如何验证你的解当你写出代码后如何确保它是正确的除了肉眼检查输出可以编写简单的验证函数bool verifySolution(int c, int h, int ch) { bool condition1 (c h ch 100); bool condition2 (ch % 3 0); bool condition3 (5*c 3*h ch/3 100); // 此时ch已确保是3的倍数 return condition1 condition2 condition3; } // 在找到每组解后调用 if (verifySolution(cock, hen, chick)) { cout 验证通过: cock , hen , chick endl; }5.3 问题扩展与举一反三“百钱百鸡”是一个经典的约束满足问题。掌握它后你可以尝试解决变体锻炼建模能力“百钱百鸡”的推广“N钱M鸡”问题。即总钱数为N总鸡数为M价格不变求所有解。这时你的代码应该能通过修改常量TOTAL_MONEY和TOTAL_BIRDS来适应。价格变化如果公鸡、母鸡、小鸡的价格变为其他整数如何求解这需要你动态计算循环上限maxCocks MONEY / PRICE_COCK。增加鸡的种类如果还有“鸭”价格是4文钱一只问题变成“百钱百鸡鸭”如何求解这需要增加一个循环维度或者使用更通用的算法如回溯法。求特定解不要求所有解而是求“公鸡数量最多”或“总花费中公鸡占比最小”的解。这需要在循环中增加比较逻辑。5.4 从这个问题中学到的编程思维先建模后编码花时间在纸上理清数学关系定义好变量和约束往往能事半功倍。暴力法是起点但不是终点从最直观的解法开始然后不断问自己“有没有不必要的计算循环范围能缩小吗能用数学方法减少变量吗”边界条件与特殊值时刻考虑零值、负值、整除、溢出等情况。例如z % 3在z为负时的行为在C标准中是由实现定义的最好避免。代码的清晰性与可维护性即使是一个小程序使用有意义的变量名、添加必要注释、用常量代替魔法数字这些习惯会让你在合作中更受欢迎也让未来的你感谢现在的自己。回过头看“百钱百鸡”远不止是一个简单的循环练习题。它是一条引线串起了问题建模、算法优化、代码实现、边界处理、测试验证等多个编程核心环节。下次再遇到类似的经典题目不妨多花点时间像我们今天这样深挖下去你收获的将不仅仅是一个答案而是一套解决问题的可迁移的方法论。
![[GESP202606 四级] 扫雷](http://pic.xiahunao.cn/yaotu/[GESP202606 四级] 扫雷)
