暴力枚举算法原理及经典例题解析

暴力枚举（BF）的概念

暴力枚举也称为穷举法，是计算机算法中最基础、最直观，但也是最费劲的一种解题思路。

像我们平时没有最优解的算法题，往往都可以通过暴力枚举去算出最终结果。

• 核心思想 不靠巧妙的技巧，而是利用计算机强大的计算能力，把所有可能的情况列举出来，一个一个去验证，直到找到正确答案。

暴力枚举的算法步骤

• 列举：确定解空间的范围，列出所有可能的解候选者。
• 检验：对每一个候选者进行判断，看它是否满足题目条件。

例题讲解

经典案例讲解一：百鸡问题

洛谷百鸡问题

题目解析

我们要解决的核心问题是找到三个未知数（公鸡数量、母鸡数量、小鸡数量）。

• 假设：
  • 公鸡数量为 i
  • 母鸡数量为 j
  • 小鸡数量为 k
• 必须满足的两个等式：
  • 数量守恒：i + j + k = m（鸡的总数是 m）
  • 价格守恒：i * x + j * y + k / z = n（总花费是 n）
• 隐含条件：
  • k 必须能被 z 整除（因为题目说 z 只小鸡 1 元，如果买的小鸡数量不是 z 的倍数，价格就不是整数，这在古代数学题中通常隐含价格为整数，且代码中 k/z 若不能整除会有精度问题，需特别判断）
  • i, j, k 必须是非负整数。

思路方案

• 方案 A：三层循环

  • 写三层 for 循环
  • 时间复杂度：O(m^3)
  • 效率低，不推荐。

• 方案 B：两层循环

  • 时间复杂度：O(m^2)

#include <stdio.h>

int main() {
    // 定义变量
    // x: 公鸡单价, y: 母鸡单价, z: z 只小鸡 1 元
    // n: 总钱数, m: 总鸡数
    int x, y, z, n, m;
    
    
     ((, &x, &y, &z, &n, &m) != ) {
         ;
    }
    
     count = ; 
    
    
    
     ( i = ; i <= m; i++) {
        
        
         ( j = ; j <= m - i; j++) {
            
             k = m - i - j;
            
            
            
            
             (k % z ==  && (i * x + j * y + k / z == n)) {
                count++; 
            }
        }
    }
    
    
    (, count);
     ;
}