### 问题解构 “百钱买百鸡”是一个经典的中国古代数学问题，源于《张丘建算经》。其核心是求解一个**不定方程**的非负整数解。问题描述如下： > 公鸡每只5钱，母鸡每只3钱，小鸡三只1钱。用100钱买100只鸡，问公鸡、母鸡、小鸡各有多少只？ 设公鸡数量为 \( x \)，母鸡数量为 \( y \)，小鸡数量为 \( z \)，则可建立方程组： 1. \( x + y + z = 100 \) （总鸡数为100只） 2. \( 5x + 3y + \frac{z}{3} = 100 \) （总钱数为100钱） 这是一个包含三个未知数但只有两个独立方程的方程组，属于不定方程，通常有多个解。我们的目标是找出所有满足条件的非负整数解 \((x, y, z)\) [ref_3]。 ### 方案推演与代码实现 解决此问题的核心是**遍历所有可能的整数组合**，并验证是否满足上述两个方程。最直观的方法是使用三重循环，分别遍历公鸡、母鸡和小鸡的可能数量。然而，直接三重循环效率低下，需要进行优化。 #### 1. 基础三重循环法（低效示例） 此方法逻辑简单，但循环次数极多（最多可达 \(101 \times 101 \times 101 \approx 1,030,301\) 次），仅用于展示问题本质。 ```python # 基础三重循环法（效率低下，仅作演示） print("基础三重循环法结果：") for x in range(0, 101): # 公鸡数量从0到100 for y in range(0, 101): # 母鸡数量从0到100 for z in range(0, 101): # 小鸡数量从0到100 if (x + y + z == 100) and (5*x + 3*y + z/3 == 100): print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只") ``` *运行此代码将找到所有解，但计算量巨大。* #### 2. 优化双重循环法（推荐） 根据方程 \( x + y + z = 100 \)，可以得到 \( z = 100 - x - y \)。将此关系代入钱数方程，可以将三重循环优化为双重循环，并提前根据价格限制每种鸡的数量上限，显著减少计算量 [ref_1][ref_4]。 **优化思路：** * **公鸡上限**：即使全部钱都买公鸡，最多买 \( \lfloor 100 / 5 \rfloor = 20 \) 只。 * **母鸡上限**：即使全部钱都买母鸡，最多买 \( \lfloor 100 / 3 \rfloor \approx 33 \) 只。 * **小鸡数量**：由 \( z = 100 - x - y \) 直接计算得出。 * **验证条件**：只需验证钱数方程，并确保小鸡数量是3的倍数（因为小鸡只能按3的倍数购买）。 ```python # 优化后的双重循环法 print("优化双重循环法结果：") for x in range(0, 21): # 公鸡数量范围：0 到 20 for y in range(0, 34): # 母鸡数量范围：0 到 33 z = 100 - x - y # 计算小鸡数量 if z < 0: # 小鸡数量不能为负 continue # 检查总价是否为100钱，并且小鸡数量是3的倍数 if (5*x + 3*y + z/3 == 100) and (z % 3 == 0): print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只") ``` *此方法循环次数最多为 \(21 \times 34 = 714\) 次，效率极高 [ref_1]。* #### 3. 进一步优化：单循环法 利用两个方程，可以推导出 \( x \) 和 \( y \) 的直接关系，从而将循环减至一重。 由方程组： \[ \begin{cases} x + y + z = 100 \\ 5x + 3y + \frac{z}{3} = 100 \end{cases} \] 将第一个方程乘以3后与第二个方程联立消去 \( z \)： \[ 15x + 9y + (100 - x - y) = 300 \] 简化得： \[ 14x + 8y = 200 \] 进一步化简： \[ 7x + 4y = 100 \] 由此可得 \( y = (100 - 7x) / 4 \)。由于 \( y \) 必须是非负整数，因此 \( (100 - 7x) \) 必须能被4整除且结果非负 [ref_2][ref_5]。 ```python # 优化单循环法 print("优化单循环法结果：") for x in range(0, 21): # 公鸡数量范围：0 到 20 if (100 - 7*x) % 4 == 0: # 确保 (100-7x) 能被4整除 y = (100 - 7*x) // 4 z = 100 - x - y if y >= 0 and z >= 0: # 确保母鸡和小鸡数量非负 print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只") ``` *此方法仅需循环21次，是最高效的数学解析解法。* ### 结果对比与分析 执行上述优化后的双重循环或单循环代码，将得到完全相同的四组解： | 公鸡数量 (x) | 母鸡数量 (y) | 小鸡数量 (z) | 验证 (总只数/总钱数) | | :--- | :--- | :--- | :--- | | 0 | 25 | 75 | 100 / 100 | | 4 | 18 | 78 | 100 / 100 | | 8 | 11 | 81 | 100 / 100 | | 12 | 4 | 84 | 100 / 100 | **关键点总结：** 1. **算法效率至关重要**：从最初可能的上百万次计算，通过数学关系优化到714次（双重循环），再到仅21次（单循环），体现了算法优化对程序性能的巨大提升 [ref_1][ref_4][ref_6]。 2. **约束条件的使用**：充分利用价格约束确定循环范围（公鸡0~20，母鸡0~33），以及小鸡数量必须为3的倍数的隐含条件，是减少无效计算的关键 [ref_3]。 3. **数学推导简化问题**：将不定方程化简为 \( 7x + 4y = 100 \) 是最高效的解法，它直接将问题转化为寻找满足整除条件的整数解，极大地降低了计算复杂度 [ref_2][ref_5]。 因此，解决“百钱买百鸡”问题不仅是一个编程练习，更是对**逻辑思维**和**算法优化能力**的很好训练。在实际编程中，应优先采用双重循环或单循环的优化方案。