C++算法入门：从百钱买鸡问题掌握枚举、剪枝与数学建模

1. 从“百钱买鸡”聊起一个经典问题如何串起C算法学习的脉络最近在整理自己的C学习笔记翻到了一个非常经典的入门级算法问题——“百钱买鸡”。这问题乍一看简单甚至有点“古老”但它就像一把钥匙能打开C算法学习中的好几扇门。很多朋友刚开始学C语法刚熟悉一碰到“算法”两个字就有点发怵觉得高深莫测。其实不然算法就是解决问题的步骤和方法而“百钱买鸡”就是一个绝佳的起点。它不涉及复杂的数据结构却能让你清晰地体会到暴力枚举、循环优化、数学建模这些核心算法思想并用C代码将其实现。无论你是正在啃《C Primer》的学生还是想重温基础、准备技术面试的开发者通过彻底吃透这个“小”问题都能对C编程和算法思维有一个扎实的、感性的认识。我们今天不搞花架子就从这个具体的问题出发一步步拆解看看如何用C写出高效的解法并从中提炼出可迁移的编程经验。2. 问题拆解把现实问题翻译成计算机语言2.1 “百钱买鸡”到底在问什么先明确一下题目这是我国古代一道经典的数学问题通常的描述是公鸡5文钱一只母鸡3文钱一只小鸡1文钱三只。现在要用100文钱正好买100只鸡请问公鸡、母鸡、小鸡各应该买多少只这里有几个关键约束条件我们必须先把它从自然语言“翻译”成数学语言这是算法设计的第一步数量约束公鸡数 母鸡数 小鸡数 100只。金额约束5 * 公鸡数 3 * 母鸡数 (1/3) * 小鸡数 100文。隐含约束所有鸡的数量都必须是非负整数。特别是小鸡因为1文钱买3只所以小鸡的数量必须是3的倍数否则钱就无法正好花完。很多初学者会直接开始写循环但更好的习惯是先进行数学化简。设公鸡数量为x母鸡为y小鸡为z。根据上述条件我们可以得到方程组x y z 100 5x 3y z/3 100第二个方程两边乘以3消去分母15x 9y z 300。 然后用第一个方程z 100 - x - y代入第二个方程得到15x 9y (100 - x - y) 300。 化简后得到14x 8y 200 进一步除以27x 4y 100。看问题瞬间清晰了我们从三元一次不定方程组化简为了一个二元一次方程7x 4y 100并且x,y,z均为非负整数z是3的倍数。这个化简过程本身就是“数学建模”和“优化问题规模”的体现。在真正的算法竞赛或工程中这种前置的数学分析往往能极大降低后续计算的复杂度。2.2 确定算法思路从“暴力破解”到“精确打击”面对化简后的方程7x 4y 100我们可以构思几种C解法思路一三重循环暴力枚举最直接的想法既然不知道各买多少那就把所有可能都试一遍。让x从0循环到100y从0循环到100z从0循环到100检查是否同时满足两个方程。这需要循环101 * 101 * 101 ≈ 100万次。虽然对现代计算机来说瞬间完成但这是一种非常低效的“穷举”思维没有利用任何已知条件。思路二二重循环利用总数约束既然x y z 100那么当x和y确定后z自然等于100 - x - y。这样我们就可以省去最内层关于z的循环只需要双重循环遍历x和y然后计算z并判断金额约束和z%30。循环次数降至约100 * 100 1万次。思路三单重循环利用数学关系这是我们化简方程的目标。由7x 4y 100可得y (100 - 7x) / 4。那么我们只需要遍历x然后计算y再根据x和y计算z并验证y是否为整数、非负以及z是否为非负整数且是3的倍数。x的范围是多少因为7x 100且x非负所以x的范围是[0, 14]。我们只需要最多循环15次从百万次到一万次再到十五次效率的提升是指数级的。这清晰地展示了算法优化的力量通过分析问题本质减少不必要的计算。在C学习初期就建立这种“先思考再编码”的意识至关重要。3. C代码实现与逐行精讲接下来我们用C将上述思路实现。我会给出不同优化程度的代码并详细解释每一行代码的意图和C知识点。3.1 基础版三重循环暴力法虽然效率最低但作为理解循环和条件判断的起点我们看一下它的样子。#include iostream using namespace std; int main() { cout 公鸡\t母鸡\t小鸡 endl; // 制表符\t用于对齐输出 for (int x 0; x 100; x) { // x: 公鸡数量 for (int y 0; y 100; y) { // y: 母鸡数量 for (int z 0; z 100; z) { // z: 小鸡数量 // 判断条件总数为100总钱数为100且小鸡数是3的倍数 if ( (x y z 100) (5*x 3*y z/3.0 100) // 注意z/3.0 确保浮点除法 (z % 3 0) ) { cout x \t y \t z endl; } } } } return 0; }代码精讲与避坑指南循环变量与范围for (int x 0; x 100; x)。这里定义了循环变量x从0到100包含。x是前缀自增在本例中与x效果相同但在C社区对于非类类型的迭代更推荐使用i习惯更好。条件判断中的陷阱5*x 3*y z/3.0 100。这是最容易出错的地方。如果写成z/3在C中两个整数相除结果仍是整数向下取整。当z1时z/3等于0这会导致计算错误。必须将除数或被除数之一转换为浮点数如z/3.0以执行浮点除法。但浮点数比较相等 () 又存在精度风险。更严谨的做法是利用之前推导的整数方程15x 9y z 300来判断完全避免浮点数。输出格式化使用\t制表符可以简单对齐各列数据使结果更易读。注意实际运行这段代码你会发现它非常慢相对于后两种方法。在算法设计中能明显感知到效率差异的代码就是我们需要优化的对象。3.2 优化版二重循环与单重循环二重循环实现#include iostream using namespace std; int main() { cout 公鸡\t母鸡\t小鸡 endl; for (int x 0; x 100; x) { for (int y 0; y 100; y) { int z 100 - x - y; // 利用总数约束直接算出z if (z 0) continue; // 提前剪枝如果z为负跳过后续判断 // 判断金额约束和小鸡数量是3的倍数 if ( (5*x 3*y z/3.0 100) (z % 3 0) ) { cout x \t y \t z endl; } } } return 0; }优化点1. 省去一层循环。2. 增加了if (z 0) continue;这称为剪枝。当z已经为负数时金额约束肯定不满足直接跳过本次循环的剩余部分进入下一次迭代节省了不必要的计算。单重循环最优解实现#include iostream using namespace std; int main() { cout 公鸡\t母鸡\t小鸡 endl; for (int x 0; x 14; x) { // 7x 100, 所以x最大为14 // 根据方程 7x 4y 100 推导出 y int remainder 100 - 7 * x; if (remainder % 4 ! 0) continue; // y必须为整数 int y remainder / 4; if (y 0) continue; // y必须非负 int z 100 - x - y; if (z 0 || z % 3 ! 0) continue; // z必须非负且是3的倍数 // 验证金额约束虽然数学上已保证但双重验证是好习惯 if (5 * x 3 * y z / 3 100) { // 此处z是3的倍数整除安全 cout x \t y \t z endl; } } return 0; }这才是精髓所在循环范围极小化x的范围是[0, 14]基于数学推导7x 100。整数解判定if (remainder % 4 ! 0) continue;这行代码是关键。它判断(100 - 7x)是否能被4整除不能整除意味着y不是整数直接舍弃该x值。这避免了无效的浮点数运算和后续判断。多重约束检查依次检查y非负、z非负且为3的倍数。这种分步检查、提前退出的模式在复杂条件判断中非常高效。最终验证尽管从方程推导来看满足前述条件的解一定满足金额约束但最后再加一道验证是稳健的编程习惯可以防止推导或编码过程中的疏忽。运行这段代码你会立即得到全部四组解公鸡 母鸡 小鸡 0 25 75 4 18 78 8 11 81 12 4 844. 算法思想延伸从枚举到优化策略通过“百钱买鸡”问题我们可以提炼出几种通用的算法思想和C编程技巧4.1 枚举法暴力搜索及其适用边界枚举法也叫穷举法就是逐一尝试所有可能的解并验证哪些满足条件。我们的“三重循环”版本就是最原始的枚举。何时用当问题规模很小或者暂时想不到更优解法时枚举是一个可靠的起点。它保证你能找到解如果存在的话。C实现要点合理确定循环变量的上下界是优化枚举的第一步。比如买鸡问题公鸡不可能超过20只因为100文全买公鸡这就是一个比100更紧的界。在二重循环版本中我们甚至可以根据x的值进一步缩小y的循环范围。经验心得永远不要写无脑的全范围枚举。哪怕是用暴力法也要先动笔算一算尽可能收紧循环的边界。这能立即提升代码效率也是面试中展现你思维严密性的地方。4.2 约束传递与剪枝剪枝是优化搜索算法的核心技术。我们在二重循环中if (z 0) continue;就是一次剪枝。核心思想在搜索过程中一旦发现当前部分解已经不可能导致最终的正确解就立即回溯或跳过不再继续深入。在本题中的应用除了z0我们还可以在循环开始前计算更紧的界限。例如对于x公鸡其上限不仅是100由5x 100可得x 20。由7x 4y 100且y0可得x 14。使用更严格的14作为上限就是通过数学分析完成的“预剪枝”。更广泛的场景在深度优先搜索DFS、回溯算法解决数独、八皇后等问题时剪枝是保证算法能在可接受时间内运行的关键。4.3 数学建模与问题转化这是本问题带给我们的最高阶启示。将“百钱买百鸡”这个应用题转化为二元一次不定方程7x 4y 100是质的飞跃。价值它将一个需要搜索三维空间x, y, z的问题降维到了只需要搜索一维空间x。复杂度从 O(n³) 降低到了 O(n)。C编程启示在动手写代码之前务必先进行纸笔分析。尝试用数学公式描述约束条件看看是否能合并、化简、推导出新的、更简单的约束。这个过程本身就是在设计算法。一个相关案例判断一个数是否为质数。最笨的方法是让i从2循环到n-1看能否整除。优化一点是循环到sqrt(n)。这就是通过数学分析因数的对称性来缩小搜索范围。5. 不止于求解C工程化与扩展思考一个简单的算法题完全可以作为练习C工程化编码习惯的起点。5.1 代码封装与函数化好的代码不是一堆语句堆在main函数里。我们可以将求解逻辑封装成函数提高可读性和复用性。#include iostream #include vector #include tuple // 用于返回多个值 using namespace std; // 使用单重循环数学优化的方法求解并返回所有解的向量 vectortupleint, int, int solveChickenProblem(int totalMoney, int totalChickens, int priceCock, int priceHen, int priceChickPerThree) { vectortupleint, int, int solutions; // 根据推导公鸡的最大数量由价格和总钱数决定 // 这里为了通用性我们采用一个稍宽但合理的范围并在循环内做快速判断 int maxCock totalMoney / priceCock; for (int cock 0; cock maxCock; cock) { // 推导核心方程: (priceCock - priceChickPerThree/3)*cock (priceHen - priceChickPerThree/3)*hen totalMoney - (priceChickPerThree/3)*totalChickens // 简化处理本例中 priceChickPerThree1, 所以 priceChickPerThree/3 不是整数通用推导较复杂。 // 我们采用更通用的二重循环剪枝版本作为函数实现以展示思路。 // 注意这里为了示例函数封装我们实现一个通用性更强的二重循环剪枝版本。 int maxHen (totalMoney - priceCock * cock) / priceHen; for (int hen 0; hen maxHen; hen) { int remainingMoney totalMoney - priceCock * cock - priceHen * hen; int chicks totalChickens - cock - hen; if (chicks 0 || chicks % 3 ! 0) continue; if (remainingMoney (chicks / 3) * priceChickPerThree) { // 确保小鸡总价计算正确 solutions.emplace_back(cock, hen, chicks); } } } return solutions; } int main() { int totalMoney 100; int totalChickens 100; int priceCock 5; int priceHen 3; int priceChickPerThree 1; // 三只小鸡的价格 auto results solveChickenProblem(totalMoney, totalChickens, priceCock, priceHen, priceChickPerThree); cout 找到 results.size() 组解 endl; cout 公鸡\t母鸡\t小鸡 endl; for (const auto sol : results) { cout get0(sol) \t get1(sol) \t get2(sol) endl; } // 扩展测试如果钱是200文买200只鸡呢 cout \n--- 扩展测试200文买200只鸡 --- endl; auto results2 solveChickenProblem(200, 200, 5, 3, 1); cout 找到 results2.size() 组解 endl; for (const auto sol : results2) { cout get0(sol) \t get1(sol) \t get2(sol) endl; } return 0; }封装带来的好处清晰的责任分离main函数负责输入输出和业务逻辑调度求解算法封装在独立函数中。可测试性可以轻松编写测试用例验证函数在不同参数下的正确性。可扩展性如代码所示改变总钱数、总鸡数、价格等参数非常容易无需修改算法函数内部逻辑。使用现代C特性vectortuple...作为返回值安全地返回多组解。emplace_back直接在容器内构造元素比push_back更高效。5.2 性能考量与常数优化即使在单重循环的极致优化下我们仍可以关注一些C层面的“微操作”循环变量类型使用int足够。在确信无负数且范围不大时使用unsigned int或更小的short理论上可能有些许好处但现代编译器优化后差异极小可读性优先。避免重复计算在循环if (5 * x 3 * y z / 3 100)中5*x、3*y会被重复计算。如果循环次数很多可以预先计算5*x并存储在一个临时变量中。不过在本例中循环仅15次完全没必要。输出效率如果解非常多例如在更大规模的问题中频繁调用cout可能成为瓶颈。可以考虑先将结果存入stringstream或vector最后一次性输出。但同样对于本题无需过度优化。实操心得在算法学习中首先要保证正确性其次是清晰性最后才是优化。不要过早陷入“奇技淫巧”的微观优化。像“百钱买鸡”问题从三重循环优化到单重循环这种算法复杂度的优化从O(n³)到O(n)带来的性能提升远远大于把i改成i或者省掉一个临时变量。分清主次抓住主要矛盾。5.3 问题变种与思维拓展掌握了基本解法我们可以思考一些变种问题进一步锻炼思维求所有解中公鸡数量最多的方案在输出解的同时记录x的最大值即可。这引入了“在多个可行解中寻找最优解”的思路通向“优化问题”。如果小鸡不是3只1文而是4只1文或者公鸡、母鸡价格变化方程如何推导程序如何通用化这促使我们思考算法抽象就像上面封装函数时尝试的那样。如果要求公鸡、母鸡、小鸡都必须至少买一只呢这只需要修改循环的起始值x从1开始y从1开始和相应的条件判断即可。这练习了约束条件的增减。“百钱买百鸡”属于“整数线性规划”问题的特例。了解这一点后可以顺藤摸瓜地去学习更通用的算法如分支定界法。这为我们打开了更广阔的算法世界的大门。6. 常见疑问与调试技巧在实际编写和运行这类算法代码时新手常会遇到一些问题Q1: 为什么我的程序运行后什么都没输出或者输出不对A1: 这是最典型的问题。请按以下步骤排查检查浮点数比较如果你使用了z/3.0 100这样的判断由于浮点精度问题可能因为极小的误差导致条件不成立。强烈建议使用整数运算即判断5*x 3*y z/3 100 z % 3 0。注意这里z/3是整数除法但前提是z % 3 0已确保z能被3整除所以z/3就是小鸡花费的钱数。检查循环边界确认你的x,y,z的循环范围是否覆盖了所有可能。太窄会漏解太宽会降低效率。使用调试输出在循环内关键位置添加临时输出打印x,y,z的值以及关键条件判断的结果这是最直接的“肉眼调试法”。Q2: 我感觉我的算法逻辑是对的但结果少了一两组解为什么A2: 大概率是约束条件没考虑全。在“百钱买鸡”问题中最容易被忽略的约束就是“小鸡数量必须是3的倍数”。如果你只用了5x 3y z/3 100这个条件当z不是3的倍数时z/3的整数除法会截断小数部分可能导致错误的解被计入。务必加上z % 3 0的判断。Q3: 如何让程序运行得更快A3: 对于本题单重循环已经快到无法感知。但建立性能意识很重要减少循环层数这是最大的优化方向。减少循环次数通过数学分析收紧循环变量上下界。循环内减少计算将循环内不变的表达式提到循环外。使用更高效的数据结构和算法本题不涉及但在复杂问题中这是根本。Q4: 学习这类基础算法题对实际C项目开发有用吗A4: 非常有用但这种“有用”是间接且深远的。锻炼问题分解能力将模糊的需求转化为清晰的数学约束和计算步骤这是软件工程师的核心能力。培养优化思维在资源时间、空间有限的情况下寻求最优解这种思维在系统设计、性能调优中无处不在。夯实编码基础熟练使用循环、条件判断、函数封装是写好任何C代码的基石。为学习高级算法铺路枚举、剪枝、数学建模是回溯、动态规划、线性规划等高级算法的基础。通过简单问题理解这些思想再学习复杂算法就不会那么抽象。最后我想说的是“百钱买鸡”这类问题就像练武时的扎马步看起来平淡无奇却是所有高深功夫的根基。在C和算法的学习路上耐下性子把每一个这样的“小问题”吃透、嚼烂理解其背后的每一层逻辑比囫囵吞枣地刷十道难题更有价值。当你再遇到更复杂的问题时你会自然而然地想起“哦这个约束有点像买鸡问题里的那个方程我可以试试化简”或者“这里搜索空间太大我得像剪枝那样提前排除一些不可能的情况”。这种思维的迁移才是算法学习带给我们的真正财富。