暴力枚举算法详解
暴力枚举(Brute Force),也称为穷举法,是计算机算法中最基础、最直观的一种解题思路。虽然它听起来有些'笨',但在没有更优解法或数据规模可控时,利用计算机强大的计算能力遍历所有可能性,往往是最稳妥的方案。
核心思想与步骤
暴力枚举的核心在于不依赖巧妙的技巧,而是依靠程序遍历所有可能的情况,逐一验证是否满足条件。
- 列举:确定解空间的范围,列出所有可能的候选解。
- 检验:对每一个候选者进行判断,看它是否符合题目要求。
经典案例实战
案例一:百鸡问题
这是一道经典的数学题,通常出现在算法入门阶段。我们需要找到公鸡、母鸡和小鸡的数量组合。
问题分析
- 设公鸡数量为
i,母鸡为j,小鸡为k。 - 约束条件:
- 数量守恒:
i + j + k = m(总鸡数) - 价格守恒:
i * x + j * y + k / z = n(总花费,其中 z 只小鸡 1 元)
- 数量守恒:
- 隐含条件:
k必须能被z整除,且所有变量为非负整数。
优化思路
直接写三层循环时间复杂度为 O(m³),效率较低。由于 k = m - i - j,我们可以将第三层循环转化为计算,降低到 O(m²)。
#include <stdio.h>
int main() {
int x, y, z, n, m;
// 读取输入:x(公鸡单价), y(母鸡单价), z(z 只小鸡 1 元), n(总钱数), m(总鸡数)
if (scanf("%d %d %d %d %d", &x, &y, &z, &n, &m) != 5) {
return 1;
}
int count = 0;
// 第一层:枚举公鸡数量 i
for (int i = 0; i <= m; i++) {
// 第二层:枚举母鸡数量 j
// 母鸡数量加上公鸡数量不能超过总数 m
for (int j = 0; j <= m - i; j++) {
// 剩下的就是小鸡数量 k
int k = m - i - j;
(k % z == && (i * x + j * y + k / z == n)) {
count++;
}
}
}
(, count);
;
}


