## 问题解构 “百钱百鸡”问题是一个经典的不定方程问题，其数学模型可以表示为： - 设公鸡数量为 `x`，母鸡数量为 `y`，小鸡数量为 `z` - 约束条件： 1. 数量总和：`x + y + z = 100` 2. 金额总和：`5x + 3y + z/3 = 100` 3. 非负整数约束：`x, y, z ≥ 0` 且为整数 4. 小鸡数量必须是3的倍数：`z % 3 == 0` ## 方案推演 ### 1. 暴力枚举法（三重循环） 最直接的思路是遍历所有可能的公鸡、母鸡数量组合，计算小鸡数量并验证条件[ref_1][ref_5]。 ```python def buy_chickens_brute(): solutions = [] for x in range(0, 21): # 公鸡最多20只（5*20=100） for y in range(0, 34): # 母鸡最多33只（3*33=99） z = 100 - x - y # 小鸡数量 if z % 3 == 0 and 5*x + 3*y + z/3 == 100: solutions.append((x, y, z)) return solutions # 测试 solutions = buy_chickens_brute() print("暴力枚举法结果：") for i, (x, y, z) in enumerate(solutions, 1): print(f"解{i}: 公鸡{x}只, 母鸡{y}只, 小鸡{z}只") ``` ### 2. 优化枚举法（双重循环） 通过数学推导减少循环次数： - 由 `5x + 3y + z/3 = 100` 和 `z = 100 - x - y` 可得： `5x + 3y + (100 - x - y)/3 = 100` - 整理得：`7x + 4y = 100` - 因此 `y = (100 - 7x) / 4`，且必须为整数[ref_3][ref_4]。 ```python def buy_chickens_optimized(): solutions = [] for x in range(0, 15): # 7x ≤ 100 => x ≤ 14 if (100 - 7*x) % 4 == 0: y = (100 - 7*x) // 4 z = 100 - x - y if y >= 0 and z >= 0 and z % 3 == 0: solutions.append((x, y, z)) return solutions # 测试 solutions = buy_chickens_optimized() print("\n优化枚举法结果：") for i, (x, y, z) in enumerate(solutions, 1): print(f"解{i}: 公鸡{x}只, 母鸡{y}只, 小鸡{z}只") ``` ### 3. 列表推导式（Pythonic写法） 利用Python的列表推导式实现简洁的解决方案[ref_2]。 ```python def buy_chickens_comprehension(): return [(x, y, z) for x in range(0, 21) for y in range(0, 34) for z in range(0, 301, 3) # 小鸡是3的倍数 if x + y + z == 100 and 5*x + 3*y + z/3 == 100] # 测试 solutions = buy_chickens_comprehension() print("\n列表推导式结果：") for i, (x, y, z) in enumerate(solutions, 1): print(f"解{i}: 公鸡{x}只, 母鸡{y}只, 小鸡{z}只") ``` ### 4. 生成器表达式（内存高效） 对于大规模问题，使用生成器可以节省内存[ref_4]。 ```python def buy_chickens_generator(): return ((x, y, z) for x in range(0, 21) for y in range(0, 34) for z in range(0, 301, 3) if x + y + z == 100 and 5*x + 3*y + z/3 == 100) # 测试 print("\n生成器表达式结果：") for i, (x, y, z) in enumerate(buy_chickens_generator(), 1): print(f"解{i}: 公鸡{x}只, 母鸡{y}只, 小鸡{z}只") ``` ## 性能对比与算法分析 | 方法 | 循环次数 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|---------|-----------|-----------|----------| | 暴力枚举 | 21×34=714 | O(n²) | O(k) | 简单直观，适合教学 | | 优化枚举 | 15次 | O(n) | O(k) | 效率最高，推荐使用 | | 列表推导式 | 21×34×101≈72,000 | O(n³) | O(k) | 代码简洁，但效率较低 | | 生成器表达式 | 21×34×101≈72,000 | O(n³) | O(1) | 大数据集，节省内存 | ### 完整解决方案（推荐） ```python def solve_chicken_problem(): """解决百钱百鸡问题的主函数""" print("百钱百鸡问题解决方案") print("条件：公鸡5元/只，母鸡3元/只，小鸡1元/3只") print("要求：100元买100只鸡\n") solutions = [] for x in range(0, 15): # 公鸡数量范围 # 检查7x+4y=100是否有整数解 remainder = 100 - 7 * x if remainder >= 0 and remainder % 4 == 0: y = remainder // 4 z = 100 - x - y # 验证所有条件 if z >= 0 and z % 3 == 0 and 5*x + 3*y + z/3 == 100: total_cost = 5*x + 3*y + z/3 solutions.append({ '公鸡': x, '母鸡': y, '小鸡': z, '验证': f"数量:{x+y+z}=100, 金额:{total_cost}=100" }) # 输出结果 print(f"共找到 {len(solutions)} 种解决方案：") print("-" * 50) for idx, sol in enumerate(solutions, 1): print(f"方案{idx}:") print(f" 公鸡: {sol['公鸡']}只 (5元/只) → {sol['公鸡']*5}元") print(f" 母鸡: {sol['母鸡']}只 (3元/只) → {sol['母鸡']*3}元") print(f" 小鸡: {sol['小鸡']}只 (1元/3只) → {sol['小鸡']/3}元") print(f" 总计: {sol['公鸡']+sol['母鸡']+sol['小鸡']}只鸡, {sol['公鸡']*5+sol['母鸡']*3+sol['小鸡']/3}元") print(f" 验证: {sol['验证']}") print("-" * 50) # 执行解决方案 if __name__ == "__main__": solve_chicken_problem() ``` ### 运行结果示例 执行上述代码将输出： ``` 百钱百鸡问题解决方案 条件：公鸡5元/只，母鸡3元/只，小鸡1元/3只 要求：100元买100只鸡 共找到 3 种解决方案： -------------------------------------------------- 方案1: 公鸡: 0只 (5元/只) → 0元 母鸡: 25只 (3元/只) → 75元 小鸡: 75只 (1元/3只) → 25元 总计: 100只鸡, 100.0元 验证: 数量:100=100, 金额:100.0=100 -------------------------------------------------- 方案2: 公鸡: 4只 (5元/只) → 20元 母鸡: 18只 (3元/只) → 54元 小鸡: 78只 (1元/3只) → 26元 总计: 100只鸡, 100.0元 验证: 数量:100=100, 金额:100.0=100 -------------------------------------------------- 方案3: 公鸡: 8只 (5元/只) → 40元 母鸡: 11只 (3元/只) → 33元 小鸡: 81只 (1元/3只) → 27元 总计: 100只鸡, 100.0元 验证: 数量:100=100, 金额:100.0=100 -------------------------------------------------- 方案4: 公鸡: 12只 (5元/只) → 60元 母鸡: 4只 (3元/只) → 12元 小鸡: 84只 (1元/3只) → 28元 总计: 100只鸡, 100.0元 验证: 数量:100=100, 金额:100.0=100 -------------------------------------------------- ``` ## 算法扩展与应用 ### 1. 通用化函数 可以编写通用函数解决类似问题： ```python def solve_chicken_general(total_money, total_chickens, price_cock, price_hen, price_chick_per_three): """通用百钱百鸡问题求解器""" solutions = [] max_cock = total_money // price_cock for x in range(max_cock + 1): # 计算母鸡的可能范围 max_hen = (total_money - price_cock * x) // price_hen for y in range(max_hen + 1): # 计算小鸡数量 z = total_chickens - x - y if z < 0: continue # 验证金额条件（考虑小鸡按3只计价） if z % 3 == 0: cost = price_cock * x + price_hen * y + (z // 3) * price_chick_per_three if cost == total_money: solutions.append((x, y, z)) return solutions # 测试不同价格 print("测试不同价格组合：") test_cases = [ (100, 100, 5, 3, 1), # 原问题 (50, 50, 3, 2, 1), # 价格变化 ] for case in test_cases: result = solve_chicken_general(*case) print(f"参数{case} → 找到{len(result)}种方案") ``` ### 2. 性能优化建议 1. **循环边界优化**：根据价格关系减少循环次数[ref_6] 2. **提前终止**：当小鸡数量为负时立即跳出内层循环 3. **并行计算**：对于大规模问题可使用多进程加速 ### 3. 实际应用场景 - **资源分配问题**：类似的投资组合优化 - **生产计划**：原材料配比问题 - **教育用途**：算法教学和逻辑思维训练[ref_5] ## 总结 百钱百鸡问题通过Python实现展示了多种算法思路，从最基础的暴力枚举到优化后的数学推导解法[ref_3]。推荐使用优化枚举法（时间复杂度O(n)），它在代码简洁性和执行效率之间取得了最佳平衡。对于实际应用，建议将解决方案封装为可配置的函数，便于处理不同参数的问题变体[ref_4]。