C++ 暴力枚举算法 - L31 算法基础

📚 暴力枚举算法概述

什么是暴力枚举？

暴力枚举（Brute Force）是最直接、最简单的算法思想。它的核心思想是：列举所有可能的情况，逐一检查是否满足条件。

✅ 简单直观：容易理解和实现
✅ 保证正确：不会漏掉任何解
✅ 适用范围广：适合小规模问题
⚠️ 效率较低：时间复杂度通常较高
💡 学习价值：理解问题的基础，为优化算法打基础

💡 暴力枚举的核心：
• 枚举：列出所有可能的情况
• 验证：检查每种情况是否满足条件
• 选择：从满足条件的情况中选择最优解

暴力枚举的基本框架

// 暴力枚举的基本结构
for (int i = 起始值; i <= 结束值; i++) {
    if (满足条件(i)) {
        // 处理找到的解
        cout << "找到解：" << i << endl;
    }
}

// 多重循环枚举（多个变量）
for (int i = 起始值; i <= 结束值; i++) {
    for (int j = 起始值; j <= 结束值; j++) {
        if (满足条件(i, j)) {
            // 处理找到的解
        }
    }
}

简单示例：找最大值

#include <iostream>
using namespace std;

int main() {
    int arr[] = {3, 7, 2, 9, 1, 5};
    int n = 6;
    
    // 暴力枚举：遍历所有元素
    int maxValue = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }
    
    cout << "最大值：" << maxValue << endl;
    
    return 0;
}

⚙️ 常见应用场景

应用1：求和与统计

#include <iostream>
using namespace std;

int main() {
    // 问题：计算1到100的和
    int sum = 0;
    
    // 暴力枚举：逐个累加
    for (int i = 1; i <= 100; i++) {
        sum += i;
    }
    
    cout << "1到100的和：" << sum << endl;
    
    // 问题：统计数组中大于50的元素个数
    int arr[] = {23, 67, 45, 89, 12, 56};
    int count = 0;
    
    for (int i = 0; i < 6; i++) {
        if (arr[i] > 50) {
            count++;
        }
    }
    
    cout << "大于50的元素个数：" << count << endl;
    
    return 0;
}

应用2：查找特定值

#include <iostream>
using namespace std;

// 线性搜索：暴力枚举查找
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 找到，返回索引
        }
    }
    return -1;  // 未找到
}

int main() {
    int arr[] = {3, 7, 2, 9, 1, 5};
    int n = 6;
    int target = 9;
    
    int index = linearSearch(arr, n, target);
    
    if (index != -1) {
        cout << "找到 " << target << "，位置：" << index << endl;
    } else {
        cout << "未找到 " << target << endl;
    }
    
    return 0;
}

应用3：寻找满足条件的数

#include <iostream>
using namespace std;

int main() {
    // 问题：找出1到100之间能被7整除的数
    cout << "1-100之间能被7整除的数：" << endl;
    
    for (int i = 1; i <= 100; i++) {
        if (i % 7 == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    // 问题：找出所有水仙花数（三位数）
    // 水仙花数：各位数字的立方和等于本身
    cout << "\n水仙花数：" << endl;
    
    for (int num = 100; num <= 999; num++) {
        int hundreds = num / 100;
        int tens = (num / 10) % 10;
        int units = num % 10;
        
        if (hundreds*hundreds*hundreds + 
            tens*tens*tens + 
            units*units*units == num) {
            cout << num << " ";
        }
    }
    cout << endl;
    
    return 0;
}

🎮 互动实验：枚举演示

输入范围，查看暴力枚举过程

起始值：结束值：

输入范围后点击按钮...

🛠️ 多重循环枚举

双重循环：寻找数对

#include <iostream>
using namespace std;

int main() {
    // 问题：在数组中找到两个数，使它们的和等于目标值
    int arr[] = {2, 7, 11, 15};
    int n = 4;
    int target = 9;
    
    // 暴力枚举：检查所有数对
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                cout << "找到数对：(" << arr[i] 
                     << ", " << arr[j] << ")" << endl;
                cout << "位置：(" << i << ", " << j << ")" << endl;
            }
        }
    }
    
    return 0;
}

三重循环：寻找三元组

#include <iostream>
using namespace std;

int main() {
    // 问题：找出所有满足 a² + b² = c² 的三元组（勾股数）
    cout << "100以内的勾股数：" << endl;
    
    for (int a = 1; a <= 100; a++) {
        for (int b = a; b <= 100; b++) {
            for (int c = b; c <= 100; c++) {
                if (a*a + b*b == c*c) {
                    cout << "(" << a << ", " << b 
                         << ", " << c << ")" << endl;
                }
            }
        }
    }
    
    return 0;
}

实际应用：密码破解模拟

#include <iostream>
#include <string>
using namespace std;

// 模拟暴力破解3位数字密码
void bruteForcePassword(int correctPassword) {
    cout << "开始暴力破解..." << endl;
    
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                int password = i * 100 + j * 10 + k;
                
                if (password == correctPassword) {
                    cout << "破解成功！密码是：" 
                         << password << endl;
                    return;
                }
            }
        }
    }
}

int main() {
    int password = 527;
    bruteForcePassword(password);
    
    return 0;
}

🚀 时间复杂度分析

什么是时间复杂度？

时间复杂度描述了算法执行时间随输入规模增长的趋势。我们用大O表示法来表示。

循环层数	时间复杂度	示例	n=1000时的操作次数
单层循环	O(n)	遍历数组	1,000
双层循环	O(n²)	冒泡排序	1,000,000
三层循环	O(n³)	矩阵乘法	1,000,000,000

💡 关键要点：
• 循环嵌套层数越多，时间复杂度越高
• O(n²)比O(n)慢得多，数据量大时差异明显
• 暴力枚举通常是O(n)或O(n²)，适合小规模数据

性能对比示例

#include <iostream>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int n = 10000;
    
    // O(n) - 单层循环
    auto start1 = high_resolution_clock::now();
    long long sum1 = 0;
    for (int i = 1; i <= n; i++) {
        sum1 += i;
    }
    auto end1 = high_resolution_clock::now();
    auto duration1 = duration_cast(end1 - start1);
    
    cout << "O(n) 耗时：" << duration1.count() << " 微秒" << endl;
    
    // O(n²) - 双层循环
    auto start2 = high_resolution_clock::now();
    long long sum2 = 0;
    for (int i = 1; i <= n/100; i++) {
        for (int j = 1; j <= n/100; j++) {
            sum2 += i * j;
        }
    }
    auto end2 = high_resolution_clock::now();
    auto duration2 = duration_cast(end2 - start2);
    
    cout << "O(n²) 耗时：" << duration2.count() << " 微秒" << endl;
    
    return 0;
}

优化技巧：剪枝

#include <iostream>
using namespace std;

// 未优化的暴力枚举
void findPairs1(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {  // 检查所有组合
            if (arr[i] + arr[j] == target) {
                cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
            }
        }
    }
}

// 优化后的暴力枚举（剪枝）
void findPairs2(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {  // 避免重复检查
            if (arr[i] + arr[j] == target) {
                cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
            }
        }
    }
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int n = 4;
    int target = 9;
    
    cout << "优化前：" << endl;
    findPairs1(arr, n, target);
    
    cout << "\n优化后：" << endl;
    findPairs2(arr, n, target);
    
    return 0;
}

💡 剪枝优化：
• 避免重复检查（j从i+1开始）
• 提前终止（找到解后立即break）
• 缩小搜索范围（根据条件排除不可能的情况）

📝 实战练习

📝 理解测试

以下代码的时间复杂度是多少？

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // 执行某些操作
        }
    }
}

选择答案查看解析...

💻 综合挑战

题目：使用暴力枚举解决以下问题：
1. 找出1000以内的所有完数（完美数）
2. 完数定义：一个数等于它的所有因子（不包括自身）之和
3. 例如：6 = 1 + 2 + 3，所以6是完数
4. 输出所有完数及其因子

点击"生成代码框架"查看提示...