Course playlist
算法与描述：枚举法教程（C++版）
使用C++实现枚举算法，掌握基本思想、实现方法和应用场景
枚举法简介
枚举法（Enumeration），也称为穷举法或暴力搜索法，是一种基本的算法设计策略。它通过系统地遍历所有可能的解，从中找出满足条件的解。
枚举法的核心思想
枚举法的核心思想是"穷尽所有可能性"——通过遍历问题的所有可能解，然后检查每个解是否满足问题的条件，从而找到问题的解。
枚举法是最直观、最容易理解和实现的算法之一。在C++中，枚举法通常通过循环结构实现。
C++枚举法的特点：使用for/while循环、if条件判断、数组/容器等基本语法，易于理解和实现。
C++枚举法的基本概念
定义：枚举法是一种通过遍历所有可能情况来寻找问题解的算法策略。在C++中，通常使用嵌套循环来实现多维枚举。
枚举法的三个要素（C++视角）
1
确定解空间：使用循环变量的范围定义
2
设计搜索策略：使用for/while循环嵌套
3
制定判断条件：使用if语句检查条件
C++枚举法的基本结构
典型的C++枚举法代码结构：
#include <iostream>
using namespace std;
int main() {
// 1. 确定解空间范围
for (int i = start; i <= end; i++) {
for (int j = start2; j <= end2; j++) {
// 2. 计算或获取当前解
// 3. 检查是否满足条件
if (condition(i, j)) {
// 4. 输出或记录解
cout << "解: " << i << ", " << j << endl;
}
}
}
return 0;
}
C++枚举法示例
示例1：百钱买百鸡问题（C++实现）
问题描述：公鸡5文钱一只，母鸡3文钱一只，小鸡1文钱三只。用100文钱买100只鸡，问公鸡、母鸡、小鸡各多少只？
C++实现代码：
#include <iostream>
using namespace std;
int main() {
int count = 0; // 记录解的个数
// 枚举公鸡数量（0-20只，因为5*20=100）
for (int cock = 0; cock <= 20; cock++) {
// 枚举母鸡数量（0-33只，因为3*33≈100）
for (int hen = 0; hen <= 33; hen++) {
// 小鸡数量 = 总数 - 公鸡 - 母鸡
int chick = 100 - cock - hen;
// 检查条件：钱数正好100文，且小鸡数量是3的倍数
if (chick % 3 == 0 && cock * 5 + hen * 3 + chick / 3 == 100) {
count++;
cout << "解" << count << ": 公鸡" << cock << "只, "
<< "母鸡" << hen << "只, "
<< "小鸡" << chick << "只" << endl;
}
}
}
cout << "共有" << count << "种买法" << endl;
return 0;
}
时间复杂度分析：外层循环21次，内层循环34次，总共21×34=714次循环，O(n²)级别。
示例2：找出水仙花数（C++实现）
问题描述：水仙花数是指一个3位数，其各位数字的立方和等于该数本身。例如：153 = 1³ + 5³ + 3³。
C++实现代码：
#include <iostream>
#include <cmath> // 使用pow函数
using namespace std;
int main() {
cout << "三位数中的水仙花数有：" << endl;
int count = 0;
// 枚举所有3位数（100-999）
for (int num = 100; num <= 999; num++) {
// 分解各位数字
int hundreds = num / 100; // 百位
int tens = (num / 10) % 10; // 十位
int units = num % 10; // 个位
// 计算各位数字的立方和
int sum = pow(hundreds, 3) + pow(tens, 3) + pow(units, 3);
// 判断是否为水仙花数
if (sum == num) {
count++;
cout << "第" << count << "个: " << num
<< " = " << hundreds << "³ + "
<< tens << "³ + " << units << "³" << endl;
}
}
cout << "共有" << count << "个水仙花数" << endl;
return 0;
}
时间复杂度分析：循环900次，O(n)级别，非常高效。
示例3：简单密码破解（C++实现）
问题描述：已知一个3位数的密码锁，每位数字为0-9，尝试所有可能的组合来解锁。
C++实现代码：
#include <iostream>
#include <string>
using namespace std;
int main() {
string password = "123"; // 假设的正确密码
bool found = false;
int attempts = 0;
cout << "开始破解3位数密码..." << endl;
// 枚举所有3位数组合（000-999）
for (int i = 0; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
attempts++;
// 构造当前尝试的密码字符串
string attempt = "";
attempt += to_string(i);
attempt += to_string(j);
attempt += to_string(k);
// 检查是否匹配
if (attempt == password) {
found = true;
cout << "密码破解成功！" << endl;
cout << "密码是: " << attempt << endl;
cout << "尝试次数: " << attempts << endl;
return 0; // 找到后立即退出
}
}
}
}
if (!found) {
cout << "未找到密码！" << endl;
}
return 0;
}
时间复杂度分析：三重循环，每层10次，总共10×10×10=1000次循环，O(n³)级别。
C++枚举法的实现模式
1. 简单循环枚举
适用于解空间是一维的情况，如遍历一个范围内的所有整数。
// 找出1-1000中所有能被3和5整除的数
#include <iostream>
using namespace std;
int main() {
cout << "1-1000中能被3和5整除的数：" << endl;
for (int i = 1; i <= 1000; i++) {
if (i % 3 == 0 && i % 5 == 0) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
2. 多重循环枚举
适用于解空间是多维的情况，如组合问题、排列问题。
// 找出所有三位数ABC，满足ABC = A! + B! + C!
#include <iostream>
using namespace std;
// 计算阶乘的辅助函数
int factorial(int n) {
if (n == 0 || n == 1) return 1;
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
cout << "三位数中满足ABC = A! + B! + C! 的数：" << endl;
for (int a = 0; a <= 9; a++) {
for (int b = 0; b <= 9; b++) {
for (int c = 0; c <= 9; c++) {
int num = 100 * a + 10 * b + c;
int sumFact = factorial(a) + factorial(b) + factorial(c);
if (num == sumFact && num >= 100) { // 确保是三位数
cout << num << " = " << a << "! + "
<< b << "! + " << c << "!" << endl;
}
}
}
}
return 0;
}
3. 递归枚举
适用于解空间规模不确定或需要生成所有排列/组合的情况。
// 生成长度为n的所有二进制串
#include <iostream>
#include <string>
using namespace std;
void generateBinaryStrings(int n, string current) {
// 基础情况：达到指定长度
if (current.length() == n) {
cout << current << endl;
return;
}
// 递归生成：当前位可以是0或1
generateBinaryStrings(n, current + "0");
generateBinaryStrings(n, current + "1");
}
int main() {
int n = 3; // 生成3位二进制串
cout << "所有" << n << "位二进制串：" << endl;
generateBinaryStrings(n, "");
return 0;
}
4. 状态压缩枚举
使用二进制位来表示状态，适用于子集选择问题。
// 枚举集合{1,2,3}的所有子集
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {1, 2, 3};
int n = nums.size();
cout << "集合 {1,2,3} 的所有子集：" << endl;
// 枚举所有子集（0到2^n-1）
for (int mask = 0; mask < (1 << n); mask++) {
cout << "{";
bool first = true;
// 检查mask的每一位
for (int i = 0; i < n; i++) {
// 如果第i位为1，则包含元素nums[i]
if (mask & (1 << i)) {
if (!first) cout << ", ";
cout << nums[i];
first = false;
}
}
cout << "}" << endl;
}
return 0;
}
C++枚举法的优化技巧
C++优化原则：减少循环次数、避免重复计算、使用位运算、利用STL算法
1. 减少循环范围
示例：百钱买百鸡问题的优化
// 原始版本：x:0-20, y:0-33
// 优化版本：减少不必要的循环
#include <iostream>
using namespace std;
int main() {
int count = 0;
// 优化1：当公鸡数量增加时，母鸡的最大数量减少
for (int cock = 0; cock <= 20; cock++) {
// 优化2：根据剩余钱数计算母鸡的最大数量
int maxHen = (100 - cock * 5) / 3;
if (maxHen > 33) maxHen = 33;
for (int hen = 0; hen <= maxHen; hen++) {
int chick = 100 - cock - hen;
// 优化3：提前检查小鸡数量是否为3的倍数
if (chick % 3 != 0) continue;
if (cock * 5 + hen * 3 + chick / 3 == 100) {
count++;
cout << "公鸡" << cock << ", 母鸡" << hen << ", 小鸡" << chick << endl;
}
}
}
cout << "共有" << count << "种买法" << endl;
return 0;
}
优化效果：循环次数从714次减少到约300次
2. 预处理和记忆化
示例：计算多次查询的阶乘
// 预处理阶乘表，避免重复计算
#include <iostream>
#include <vector>
using namespace std;
int main() {
const int MAX_N = 10;
vector<long long> fact(MAX_N + 1);
// 预处理：计算0-10的阶乘
fact[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
fact[i] = fact[i-1] * i;
}
// 测试查询
int queries[] = {0, 1, 5, 7, 10};
int nQueries = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < nQueries; i++) {
int n = queries[i];
cout << n << "! = " << fact[n] << endl;
}
return 0;
}
优化效果：查询时间复杂度从O(n)降到O(1)
3. 使用位运算优化
示例：判断整数奇偶性
// 使用位运算判断奇偶性，比取模运算更快
#include <iostream>
using namespace std;
int main() {
int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(numbers) / sizeof(numbers[0]);
cout << "使用位运算判断奇偶性：" << endl;
for (int i = 0; i < n; i++) {
int num = numbers[i];
// 方法1：使用取模运算（较慢）
bool isEven1 = (num % 2 == 0);
// 方法2：使用位运算（更快）
bool isEven2 = ((num & 1) == 0);
cout << num << ": " << (isEven2 ? "偶数" : "奇数") << endl;
}
return 0;
}
优化效果：位运算通常比算术运算更快
C++枚举法的时间复杂度分析
C++中常见枚举问题的时间复杂度
| 问题类型 | C++循环结构 | 时间复杂度 | 是否可行 |
|---|---|---|---|
| 3位密码锁 | 三重for循环 | O(10³) = O(1000) | ✓ 可行 |
| 百钱买百鸡 | 双重for循环 | O(20×33) = O(660) | ✓ 可行 |
| 水仙花数 | 单重for循环 | O(900) | ✓ 可行 |
| 6位密码锁 | 六重for循环 | O(10⁶) | ✓ 可行（较慢） |
| 15个元素的子集 | 位运算枚举 | O(2¹⁵) = O(32768) | ✓ 可行 |
| 20个元素的子集 | 位运算枚举 | O(2²⁰) = O(1,048,576) | ✓ 可行 |
| 25个元素的子集 | 位运算枚举 | O(2²⁵) = O(33,554,432) | △ 勉强可行 |
| 8位密码锁 | 八重for循环 | O(10⁸) | △ 勉强可行 |
C++性能提示：现代C++编译器会进行循环优化，但嵌套循环超过3层时性能会显著下降。对于大规模枚举，应考虑算法优化或使用并行计算。
C++枚举法测试题
1. 在C++中实现百钱买百鸡问题，如果使用双重循环，外层循环变量cock的范围应该是多少？
2. 下列C++代码片段的时间复杂度是多少？
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
// 一些常数时间操作
}
}
}
3. 在C++中，哪种方法可以最有效地判断一个整数是否为偶数？
C++枚举法在线编译器
在下面编写和运行C++枚举法代码：
运行结果将显示在这里
| 题目 | 对/错/率 | 难度 | 记录 | 通过 |
|---|
| 姓名 | 分数 | 提交时间 | 操作 |
|---|