蓝桥杯 Java B 组之枚举算法（暴力破解）

Day 3：枚举算法（暴力破解）

枚举算法（Brute Force）是一种 暴力搜索 方法，它通过 遍历所有可能的情况 来找到正确答案。虽然它的 时间复杂度较高，但在 数据范围较小 时，它是一种简单且有效的解法。

本日的学习目标：

• 掌握 暴力枚举 的方法
• 优化枚举范围，提高效率
• 练习 水仙花数、百钱买百鸡 等经典问题

---

�� 一、什么是枚举算法？

枚举算法（Brute Force）即 穷举所有可能的情况，然后筛选出符合条件的解。

�� 适用场景

• 数据规模较小（n ≤ 10^4）
• 无更优算法
• 暴力法可以解决问题

---

�� 二、枚举基本模板

for (int i = 0; i < n; i++) {

    for (int j = 0; j < m; j++) {

        if (满足条件) {

            处理当前解;

        }

    }

}

�� 如何优化枚举？

1. 缩小遍历范围，减少无效计算
2. 提前终止循环，避免不必要的计算
3. 利用数学特性，减少不必要的枚举

---

�� 三、经典练习题

�� 练习 1：水仙花数

�� 题目描述

• 一个 3 位数，如果 每个数字的立方和等于它本身，就称它为 水仙花数。
• 例如：153 = 1^3 + 5^3 + 3^3，所以 153 是水仙花数。
• 求出所有 100~999 之间的水仙花数。

�� 解法分析

• 100 ≤ num ≤ 999
• 分解成 百位、十位、个位 后 求立方和
• 检查是否等于 num 本身

✅ 代码实现

public class NarcissisticNumber {

    public static void main(String[] args) {

        for (int num = 100; num <= 999; num++) {

            int a = num / 100;        // 百位

            int b = (num / 10) % 10;  // 十位

            int c = num % 10;         // 个位

            if (num == (a * a * a + b * b * b + c * c * c)) {

                System.out.println(num);

            }

        }

    }

}

✅ 优化点

• 减少重复计算，a, b, c 直接计算，而不是使用 String 转换
• 时间复杂度 O(900)，可接受

�� 练习 2：百钱买百鸡问题

�� 题目描述

• 公鸡 5 钱一只，母鸡 3 钱一只，小鸡 1 钱买 3 只。
• 用 100 钱买 100 只鸡，问所有的购买方案。

�� 解法分析

• 设：
  • x 为公鸡数量（0 ≤ x ≤ 20，因为 5x ≤ 100）
  • y 为母鸡数量（0 ≤ y ≤ 33，因为 3y ≤ 100）
  • z 为小鸡数量（z = 100 - x - y）
• 方程 5x+3y+z/3=1005x + 3y + z / 3 = 100
  • 小鸡数量必须是 3 的倍数（z % 3 == 0）

✅ 代码实现

public class HundredChickens {

    public static void main(String[] args) {

        for (int x = 0; x <= 20; x++) {  // 公鸡最多 20 只

            for (int y = 0; y <= 33; y++) {  // 母鸡最多 33 只

                int z = 100 - x - y;  // 计算小鸡数量

                if (z % 3 == 0 && (5 * x + 3 * y + z / 3 == 100)) {

                    System.out.println("公鸡: " + x + ", 母鸡: " + y + ", 小鸡: " + z);

                }

            }

        }

    }

}

✅ 优化点

• 缩小 x 和 y 的范围
• z 必须是 3 的倍数，减少不必要的计算

---

�� 四、枚举优化技巧

�� 优化 1：缩小范围

• 直接枚举所有情况会超时
• 分析问题，减少不必要的枚举
• 示例：百钱买百鸡问题 
  • x 最大值是 100/5=20
  • y 最大值是 100/3=33
  • z % 3 == 0

�� 优化 2：提前终止

• 如二分查找，若找到了目标值，直接退出循环

�� 优化 3：利用数学特性

• 例如 水仙花数，如果 num < 100，就不需要检查 num == a^3 + b^3 + c^3，直接跳过。

---

�� 五、蓝桥杯枚举常考点

考点	典型题目	优化技巧
水仙花数	153, 370, 371, 407	直接计算 a^3 + b^3 + c^3
百钱买百鸡	5x + 3y + z/3 = 100	缩小 x,y 的范围
整数拆分	100 拆分为若干整数之和	动态规划
数字统计	统计 1-1000 里 1 出现的次数	数学推导优化

---

�� 六、易错点总结

❌ 误解枚举范围

for (int x = 0; x < 100; x++) {  // ❌ 范围过大，浪费计算

✅ 优化

for (int x = 0; x <= 20; x++) {  // ✅ 设定合理范围

❌ 忘记提前终止

if (找到目标) {

    continue;  // ❌ 没有提前终止，导致无意义计算

}

✅ 优化

if (找到目标) {

    break;  // ✅ 立即终止循环

}

❌ 计算不必要的情况

for (int x = 0; x <= 100; x++) {  

    for (int y = 0; y <= 100; y++) {  

        for (int z = 0; z <= 100; z++) {  // ❌ 遍历过大

✅ 优化

for (int x = 0; x <= 20; x++) {  

    for (int y = 0; y <= 33; y++) {  

        int z = 100 - x - y;  // ✅ 直接计算 z

---

七、枚举算法框架模板

public class EnumerationTemplate {

    public static void main(String[] args) {

        // 1. 确定枚举范围

        for (int var1 = min1; var1 <= max1; var1++) {

            // 剪枝：跳过不可能的情况

            if (condition1) continue;

            for (int var2 = min2; var2 <= max2; var2++) {

                // 剪枝：进一步优化

                if (condition2) break;

                // 2. 计算候选解

                int candidate = calculate(var1, var2);

                // 3. 验证条件

                if (isValid(candidate)) {

                    System.out.println(candidate);

                }

            }

        }

    }

    private static int calculate(int a, int b) {

        return a + b; // 根据问题定义计算

    }

    private static boolean isValid(int value) {

        return value == target; // 根据问题定义验证

    }

}

八、知识点总结

• 枚举算法的基本思想：将问题的所有可能解一一列举出来，然后逐一检查是否满足条件。
• 枚举范围的确定：根据问题的条件和约束，确定变量的取值范围，避免不必要的枚举，提高算法效率。
• 变量关系的利用：分析变量之间的关系，利用这些关系减少枚举的变量数量，简化问题。

蓝桥杯常考点

• 枚举算法的应用：在蓝桥杯的题目中，经常会出现一些需要使用枚举算法解决的问题，如寻找满足特定条件的数字组合、排列等。
• 优化枚举范围：考查选手是否能够分析问题的条件，找出变量的合理取值范围，对枚举算法进行优化，避免超时。
• 边界条件处理：在枚举过程中，需要注意边界条件的处理，确保枚举的范围正确，不遗漏可能的解。

蓝桥杯易错点

• 枚举范围过大：没有对问题进行深入分析，直接枚举所有可能的情况，导致算法效率低下，在规定时间内无法得出结果。
• 边界条件错误：在确定枚举范围时，边界条件设置错误，可能会遗漏某些解或者枚举到无效的情况。
• 逻辑错误：在检查解是否满足条件时，逻辑判断出现错误，导致结果不准确。例如，在百钱买百鸡问题中，忘记检查小鸡数量是否为 3的倍数。