【信奥赛·算法基础】CSP-J 枚举算法

序言

解决问题，并不是一开始就要找到最优解，而是在不断的调试中优化，将求解过程中耗时的部分、占用空间的部分尽可能的缩小，使得程序运行起来更高效

一、定义与概念

枚举算法，也叫穷举算法，是一种简单而直接的问题求解策略。它的核心思想是逐一列举问题的所有可能解，并逐一检验每个可能解是否满足问题的要求，从而找到问题的真正解。

二、基本步骤

1. 确定枚举范围：首先要明确问题中可能解的范围。例如，在求解一个整数范围内的问题时，需要确定这个整数的取值范围。
2. 逐一列举可能解：在确定的范围内，依次列举出每一个可能的解。这可以通过循环等方式实现。
3. 检验可能解：对于每一个列举出的可能解，检验它是否满足问题的要求。如果满足要求，则该解就是问题的一个解；如果不满足要求，则继续检验下一个可能解。

三、应用示例

- 百钱百鸡问题

1. 问题描述：公鸡五文钱一只，母鸡三文钱一只，小鸡一文钱三只。用一百文钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？
2. 求解过程：
   • 确定枚举范围：因为总共只有一百文钱，所以公鸡最多买 20 只（100÷5），母鸡最多买 33 只（100÷3），小鸡最多买 300 只（100×3）。但由于要正好买一百只鸡，所以小鸡的数量是根据公鸡和母鸡的数量确定的，所以只需要枚举公鸡和母鸡的数量即可。
   • 逐一列举可能解：用双重循环分别枚举公鸡和母鸡的数量。
   • 检验可能解：对于每一组公鸡和母鸡的数量，计算出小鸡的数量，然后判断总钱数是否为一百文，总鸡数是否为一百只。如果满足条件，则这组解就是问题的一个解。
3. C++ 代码实现：

#include <iostream>
using namespace std;

int main() {
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j <= 33; j++) {
            int k = 100 - i - j;
            if (k % 3 == 0 && 5 * i + 3 * j + k / 3 == 100) {
                cout << "公鸡：" << i << "只，母鸡：" << j << "只，小鸡：" << k << "只。" << endl;
            }
        }
    }
    return 0;
}

- 水仙花数问题

1. 问题描述
   “水仙花数”是指一个三位数，其各位数字的立方和等于该数本身。例如，153 是一个水仙花数，因为 1 3 + 5 3 + 3 3 = 1 + 125 + 27 = 153 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153 13+53+33=1+125+27=153。

2. 求解思路
   使用枚举算法，从 100 到 999 逐一列举所有的三位数，对每个数分别求出其百位、十位和个位数字，然后计算这三个数字的立方和，判断是否等于该数本身。如果相等，则该数是水仙花数。

3. C++ 代码实现

#include <iostream>
using namespace std;

int main() {
    cout << "水仙花数有：";
    for (int num = 100; num <= 999; num++) {
        int a = num / 100; // 百位数字
        int b = (num / 10) % 10; // 十位数字
        int c = num % 10; // 个位数字
        if (a * a * a + b * b * b + c * c * c == num) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

四、枚举算法的特点与优势

1. 简单直观：枚举算法的实现非常简单，容易理解。对于一些小规模的问题，枚举算法可以快速地找到问题的解。
2. 确定性：只要枚举范围确定正确，并且检验条件准确，枚举算法一定能够找到问题的所有解。

五、枚举算法的局限性

1. 效率低：对于大规模问题，枚举算法的效率非常低，因为它需要逐一列举所有可能的解，这可能会导致计算时间过长。
2. 可能无法处理复杂问题：对于一些复杂的问题，可能无法确定枚举范围或者检验条件非常复杂，使得枚举算法难以应用。

最后，枚举算法是一种简单而直接的问题求解策略，适用于一些小规模、简单的问题。在使用枚举算法时，需要注意确定正确的枚举范围和检验条件，以提高算法的效率和准确性。