C++ 枚举算法实践学习笔记

一、前言

枚举算法是一种基础且实用的算法思想，通过逐一列举所有可能的情况，筛选出符合条件的解。本次结合 OpenJudge 上的几道题目，学习如何用 C++ 实现枚举算法，涵盖鸡兔同笼、两倍数对、质数和与积等场景，帮助大家理解枚举的应用。

二、鸡兔同笼（1752 题）

（一）题目分析

已知鸡和兔的脚总数 a，鸡 2 只脚、兔 4 只脚，求笼子里动物最少和最多数量。

• 最少动物数：让脚多的动物（兔）尽可能多，因为兔脚多，相同脚数下兔数量少则总动物数少。
• 最多动物数：让脚少的动物（鸡）尽可能多，相同脚数下鸡数量多则总动物数多。

（二）代码实现（带注释）

#include <iostream>
using namespace std;

int main() {
    int a; // 存储脚的总数
    cin >> a; 

    int minAnimals = 50000; // 初始化最少动物数（设较大值，方便后续更新）
    int maxAnimals = 0;     // 初始化最多动物数

    // 枚举兔子数量 i（兔最多 a/4 只，因为每只兔4只脚）
    for (int i = 0; i <= a / 4; i++) { 
        // 枚举鸡数量 j（鸡最多 a/2 只，因为每只鸡2只脚）
        for (int j = 0; j <= a / 2; j++) { 
            // 验证脚总数是否匹配
            if (i * 4 + j * 2 == a) { 
                // 更新最少动物数
                if (i + j < minAnimals) { 
                    minAnimals = i + j;
                }
                // 更新最多动物数
                if (i + j > maxAnimals) { 
                    maxAnimals = i + j;
                }
            }
        }
    }

    // 判断是否有有效解
    if (minAnimals == 50000 && maxAnimals == 0) { 
        cout << "0 0" << endl;
    } else {
        cout << minAnimals << " " << maxAnimals << endl;
    }

    return 0;
}

（三）代码逻辑说明

1. 枚举范围：
   • 兔子数量 i 范围 0 到 a/4（兔 4 只脚，最多 a/4 只）。
   • 鸡数量 j 范围 0 到 a/2（鸡 2 只脚，最多 a/2 只）。
2. 条件验证：通过 i*4 + j*2 == a 检查脚总数是否符合输入。
3. 更新最值：遍历所有可能的鸡兔数量组合，更新最少、最多动物数。

三、两倍数对（1809 题）

（一）题目分析

输入若干不同正整数（以 0 结尾），统计有多少数对满足“一个数是另一个数的两倍”。

（二）代码实现（带注释）

#include <iostream>
using namespace std;

int main() {
    int arr[20]; // 存储输入的正整数（题目说2-15个数，设20足够）
    int count = 0; // 统计符合条件的数对数量
    int n = 0; // 记录输入的有效数字个数

    // 循环输入，直到遇到0
    while (true) { 
        int num;
        cin >> num;
        if (num == 0) break; // 0 作为结束标志
        arr[++n] = num; // 存储数字，n 从1开始计数
    }

    // 双重循环枚举所有数对
    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= n; j++) { 
            // 检查是否满足“一个数是另一个数的两倍”
            if (arr[i] * 2 == arr[j]) { 
                count++;
            }
        }
    }

    cout << count << endl; // 输出结果
    return 0;
}

（三）代码逻辑说明

1. 输入处理：用 while(true) 循环持续读入数字，遇到 0 结束，并存入数组 arr。
2. 双重枚举：外层循环 i 和内层循环 j 遍历所有数对，判断 arr[i]*2 == arr[j] 是否成立。
3. 计数输出：符合条件的数对数量存入 count，最后输出。

四、质数的和与积（7827 题）

（一）题目分析

输入质数和 S，找出两个质数 i 和 j（i + j = S），使它们的积最大。

（二）关键知识：埃拉托斯特尼筛法

用于高效筛选出一定范围内的质数，步骤：

1. 创建布尔数组 isPrime，标记是否为质数，初始化为 true。
2. 把 0 和 1 标记为 false（不是质数）。
3. 从 2 开始，遍历到最大值，若当前数是质数，标记其所有倍数为 false。

（三）代码实现（带注释）

#include <iostream>
using namespace std;

int main() {
    // 标记 0~10000 是否为质数（题目说S≤10000）
    bool isPrime[10001]; 
    // 初始化：默认认为所有数是质数
    for (int i = 0; i <= 10000; i++) { 
        isPrime[i] = true;
    }
    // 0和1不是质数
    isPrime[0] = isPrime[1] = false; 

    // 埃拉托斯特尼筛法筛选质数
    for (int i = 2; i * i <= 10000; i++) { 
        if (isPrime[i]) { // 如果i是质数
            // 标记i的倍数为非质数（从i*2开始）
            for (int j = i * 2; j <= 10000; j += i) { 
                isPrime[j] = false;
            }
        }
    }

    int S; // 存储输入的质数和
    cin >> S;
    int maxProduct = 0; // 存储最大乘积

    // 枚举第一个质数i，范围到S/2（避免重复枚举，如i=3和j=7，与i=7和j=3重复）
    for (int i = 2; i <= S / 2; i++) { 
        // 检查i和S-i是否都是质数
        if (isPrime[i] && isPrime[S - i]) { 
            int product = i * (S - i); // 计算乘积
            // 更新最大乘积
            if (product > maxProduct) { 
                maxProduct = product;
            }
        }
    }

    cout << maxProduct << endl; // 输出结果
    return 0;
}

（四）代码逻辑说明

1. 筛法预处理：用埃氏筛法标记 0~10000 的质数，为后续判断提供依据。
2. 枚举质数对：遍历 2 到 S/2 的数 i，检查 i 和 S-i 是否都是质数。
3. 计算最大积：若满足条件，计算乘积并更新 maxProduct，最后输出。

五、总结

1. 枚举算法核心：通过遍历所有可能情况，筛选符合条件的解，适合问题规模不大、情况可穷尽的场景。
2. 题目共性：
   • 都用双重循环或范围枚举覆盖所有可能。
   • 结合条件判断（如脚总数匹配、数对倍数关系、质数验证）筛选有效解。
3. 优化思路：
   • 像埃氏筛法，通过预处理减少重复计算，提升效率。
   • 合理控制枚举范围（如鸡兔同笼中 i 和 j 的范围），减少不必要循环。

通过这几道题，能掌握枚举算法的基本用法，后续可尝试更复杂的枚举场景（如剪枝优化），提升编程思维～