一、课上练习

编程练习

1. 回文数个数：L2021
2. 完美数：L2022
3. 将n拆成3个数的和：L2023
4. 歌德巴赫猜想：L2024

二、知识总结

✨ 枚举法的核心思想

枚举法（也称穷举法）的核心思想是：穷举所有可能的情况，逐一检验每种情况是否满足题目条件。枚举法是最基础、最直观的算法思想，虽然效率不一定最高，但在很多问题中都能保证找到正确答案。

✨ 枚举法的原理

枚举法的一般解题思路是判断所有备选答案是否满足要求：

1. 找到枚举出所有可能性的方式：确定枚举的范围和枚举变量
2. 判断每一个备选答案是否符合要求：对每种情况进行条件检验

在实际编程中，枚举通常通过循环来实现。单层循环可以枚举一个变量的所有取值，多层嵌套循环可以枚举多个变量的组合。编写枚举法程序时，关键是要确保不遗漏、不重复地枚举所有可能性。

✨ 枚举法的优化技巧

1. 缩小枚举范围：仔细分析题目条件，尽量减少需要枚举的范围。例如枚举因子只需到 n/2 甚至 sqrt(n)。
2. 提前剪枝：当发现某种情况已经不可能满足条件时，提前跳过。例如在枚举中发现和已经超过目标值，可以直接 break。
3. 利用数学性质：例如回文数的百位等于个位，可以只枚举百位和十位，直接构造回文数，而不是枚举所有三位数再判断。

✨ 枚举法的执行示例

问题：求100到999之间所有回文数的个数。回文数是指正着读和倒着读一样的数。

分析： 三位数abc，正着读是abc，倒着读是cba，回文数要求a==c。

1int count = 0;
2for (int i = 100; i <= 999; i++) {
3    int a = i / 100;       // 百位
4    int b = (i / 10) % 10; // 十位
5    int c = i % 10;        // 个位
6    if (a == c) {
7        count++;
8    }
9}

逐步执行（部分展示）：

最终结果：100到999之间共有90个回文数。

✨ 枚举法的复杂度分析

时间复杂度

枚举法的时间复杂度取决于枚举空间的大小：

• 单层枚举：O(n)
• 双层枚举：O(n²)
• 三层枚举：O(n³)
• k 个变量的枚举：O(nᵏ)

空间复杂度

通常为 O(1)，枚举法一般只需要几个变量来记录状态，不需要额外的大数组。

优点： 思路简单直观，容易实现，能保证找到所有解。 缺点： 当枚举空间过大时效率低下，可能超时。需要通过剪枝或更优算法来优化。

✨ 枚举法的应用场景

枚举法适用于求可行解的问题，包括：

1. 求唯一解：问题只有一个正确答案
2. 求所有可行解或可行解的个数：找出所有满足条件的答案
3. 求可行解的最值：在所有可行解中找到最大或最小的

✨ 解题步骤详解：完美数问题

问题：找出1到n之间所有完美数。完美数是指一个数等于其所有真因子之和。

思考过程：

第一步：理解题意。 什么是真因子？就是除了自身以外的所有因子。例如6的真因子是1、2、3，而1+2+3=6，所以6是完美数。

第二步：确定枚举范围。 外层枚举每个数i（从2到n），内层枚举i的所有可能的真因子j（从1到i/2）。

第三步：对每个数，检验是否为完美数。 累加所有真因子的和，判断是否等于原数。

第四步：考虑优化。 枚举因子时，只需从1枚举到i/2，因为超过i/2的数不可能是i的因子（除了i本身）。

1for (int i = 2; i <= n; i++) {
2    int sum = 0;
3    for (int j = 1; j <= i / 2; j++) { // 只需枚举到 i/2
4        if (i % j == 0) {
5            sum += j;
6        }
7    }
8    if (sum == i) {
9        cout << i << endl;
10    }
11}

✨ 枚举法的常见错误

1. 枚举范围不完整：忘记包含边界值。例如题目说"1到n"，循环却写成 for(int i=1; i<n; ...)，遗漏了n。
2. 枚举范围多余：枚举了不必要的情况，导致答案重复计数或超时。
3. 条件判断写错：例如判断因子时用 i % j = 0（赋值）而不是 i % j == 0（比较）。
4. 多层循环变量混用：嵌套循环时，内外层使用了同一个变量名，导致逻辑错误。
5. 忽略时间复杂度：枚举法的效率取决于枚举空间的大小。如果枚举空间太大（例如三层循环各10^4），可能导致超时，需要考虑优化或换算法。

三、课后练习

编程练习

1. 水仙花数：L2025
2. 东东去购物：L2026