第3章 枚举基础法

3.1枚举法概述3.2枚举法实例-3.2.1百钱买百鸡-3.2.2火柴棒等式目录3.1枚举法概述枚举法，也叫穷举法，是一种非常基础但实用的算法思想。它的核心思想是在可能的解空间中逐一列举所有可能的候选解，并逐一验证是否符合问题的条件。虽然枚举法在某些情况下效率可能不高，但对于小规模数据或作为优化算法的基础，它是不可或缺的。本章我们将学习枚举法的基本概念，并通过经典案例掌握其应用与剪枝优化技巧。3.1算法基础核心思想：将所有可能的解逐一代入问题中进行验证，满足所有限定条件的解即为正确解。核心思想适用场景：解的范围已知且有限，无明显规律可循的问题。例如密码破解、组合问题等。适用场景特点：效率不高，但实用有效。依赖计算机强大的计算能力来弥补算法本身的低效。特点3.1枚举法概述题目描述鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？人工分析思路设鸡翁为x，鸡母为y，鸡雏为z，建立二元一次方程组进行求解。计算机枚举思路确定变量取值范围，逐一验证是否满足方程条件：鸡翁x范围：0~20鸡母y范围：0~33鸡雏z范围：0~3003.2.1百钱买百鸡（题目与分析）3.2.1百钱买百鸡（程序实现）优化思路：利用总数为100的条件，将三重循环优化为双重循环。确定鸡翁(x)和鸡母(y)数量后，鸡雏(z)数量可由z=100-x-y直接得出。关键点：判断条件中需包含z%3==0，确保鸡雏数量是3的倍数。for(x=0;x<=100/5;x++)//列举鸡翁的所有可能取值for(y=0;y<=100/3;y++) //列举鸡母的所有可能取值

{z=100-x-y;//根据x，y计算鸡雏的数量

if(5*x+3*y+z/3==100&&z%3==0)//找到一组正确答案

cout<<x<<""<<y<<""<<z<<endl;}3.2.2火柴棒等式（题目与分析）【题目描述】用n根火柴棒拼出形如A+B=C的等式，火柴棒必须全部用完。【分析思路】1.计算每个数字所需的火柴棒数量。2.枚举A和B的可能值，计算C=A+B。3.验证拼出A、B、C及符号所需的火柴棒总数是否等于n。【取值范围】A、B不超过1000。图3-1火柴棒数字拼法示意图核心函数：Num(x)计算拼出数字x所需的火柴棒数量，支持多位数拆分计算。intNum(intx){if(x<10)returna[x];intsum=0;while(x>0){sum+=a[x%10];x/=10;}returnsum;}主逻辑：枚举验证枚举A和B的所有可能值，计算C=A+B，验证火柴棒总数是否符合要求。for(inti=0;i<=1000;i++)for(intj=0;j<=1000;j++)if(Num(i)+Num(j)+Num(i+j)==n-4)ans++;3.2.2火柴棒等式（程序实现）枚举法优化思路1.缩小枚举范围：根据问题条件，合理估计变量的最大和最小值，避免无效的遍历。2.减少枚举变量：利用问题中的等式关系，用其他变量表示某些变量，从而减少循环层数。3.提前终止：在循环内部设置条件判断，一旦找到解或确定无解，立即终止循环。课堂小结枚举法思想：穷举所有可能解，逐一验证条件。这是最基础的算法设计思路，虽然简单但应用广泛。经典实例：掌握了“