RootStack

C++ 算法技巧 — 暴力枚举 (Brute Force Enumeration)

6分钟阅读

章节概述

暴力枚举即通过遍历所有可能的情况来寻找答案，是解决问题的最直接方法。
虽然时间复杂度较高，但思路简单不易出错，常用于小数据或作为验证工具。

核心原理

1. 枚举的数学本质

将所有可能的解空间表示为有限集合 S，然后遍历 S 中的每个元素判断是否满足条件。
复杂度: O(|S| × check_time)

2. 减少枚举量的三大技巧

技巧说明示例
缩小范围数学分析限定枚举边界三连击 a ∈ [123, 329]
利用关系用已知量推导未知量A+B=C 枚举 A,B 即可得 C
剪枝提前终止不可能的分支判断前检查边界

3. 枚举 vs 搜索

特性暴力枚举DFS/BFS
实现循环嵌套递归 + 状态
适用固定层数可变层数/图遍历
复杂度同数量级可配合剪枝

关键数据结构

P1008 [NOIP1998 普及组] 三连击

题目: 将 1~9 分成三组，每组三个数字组成三位数，且这三个三位数构成 1:2:3 的比例。

#include <iostream>
using namespace std;
 
bool check(int a, int b, int c) {
    int cnt[10] = {0};
    cnt[a / 100]++; cnt[a / 10 % 10]++; cnt[a % 10]++;
    cnt[b / 100]++; cnt[b / 10 % 10]++; cnt[b % 10]++;
    cnt[c / 100]++; cnt[c / 10 % 10]++; cnt[c % 10]++;
    for (int i = 1; i <= 9; i++)
        if (cnt[i] != 1) return false;
    return true;
}
 
int main() {
    for (int a = 123; a <= 329; a++) {
        int b = a * 2, c = a * 3;
        if (check(a, b, c))
            cout << a << " " << b << " " << c << endl;
    }
    return 0;
}

P1149 [NOIP2008 提高组] 火柴棒等式

题目: 用 n 根火柴棒拼出形如 A+B=C 的等式。

#include <iostream>
using namespace std;
 
int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
 
int need(int x) {
    if (x == 0) return cost[0];
    int sum = 0;
    while (x) { sum += cost[x % 10]; x /= 10; }
    return sum;
}
 
int main() {
    int n, ans = 0;
    cin >> n;
    n -= 4;
    for (int a = 0; a <= 999; a++)
        for (int b = 0; b <= 999; b++)
            if (need(a) + need(b) + need(a + b) == n)
                ans++;
    cout << ans << endl;
    return 0;
}

P1217 [USACO1.5] 回文质数 Prime Palindromes

题目: 找出 [a,b] 区间内所有回文质数。先枚举生成回文数，再判断质数。

#include <iostream>
using namespace std;
 
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
 
int main() {
    int a, b;
    cin >> a >> b;
    for (int d1 = 1; d1 <= 9; d1 += 2)
        for (int d2 = 0; d2 <= 9; d2++) {
            int num = d1 * 1000 + d2 * 100 + d2 * 10 + d1;
            if (num >= a && num <= b && isPrime(num))
                cout << num << endl;
        }
    for (int d1 = 1; d1 <= 9; d1 += 2)
        for (int d2 = 0; d2 <= 9; d2++)
            for (int d3 = 0; d3 <= 9; d3++) {
                int num = d1*10000 + d2*1000 + d3*100 + d2*10 + d1;
                if (num >= a && num <= b && isPrime(num))
                    cout << num << endl;
            }
    return 0;
}

P1618 三连击（升级版）

题目: 将 1~9 分成三组，构成 A:B:C 的比例。

#include <iostream>
using namespace std;
 
bool check(int a, int b, int c) {
    int cnt[10] = {0};
    cnt[a / 100]++; cnt[a / 10 % 10]++; cnt[a % 10]++;
    cnt[b / 100]++; cnt[b / 10 % 10]++; cnt[b % 10]++;
    cnt[c / 100]++; cnt[c / 10 % 10]++; cnt[c % 10]++;
    for (int i = 1; i <= 9; i++)
        if (cnt[i] != 1) return false;
    return true;
}
 
int main() {
    int A, B, C;
    bool found = false;
    cin >> A >> B >> C;
    for (int x = 123; x <= 987; x++) {
        if (x * B % A || x * C % A) continue;
        int y = x * B / A, z = x * C / A;
        if (z > 987) break;
        if (check(x, y, z)) {
            cout << x << " " << y << " " << z << endl;
            found = true;
        }
    }
    if (!found) cout << "No!!!" << endl;
    return 0;
}

推荐练习题（洛谷）

相关技巧

  • 排序: 排序后可减少枚举量
  • 搜索: DFS/BFS 是更高效的枚举方式
  • 递推递归: 递归枚举组合/排列
  • 贪心: 贪心可以避免枚举所有情况

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |

关系图谱

反向链接