I. In-Class Exercises

Programming Exercises

1. Count of Palindrome Numbers: L2021
2. Perfect Numbers: L2022
3. Split n into the Sum of 3 Numbers: L2023
4. Goldbach's Conjecture: L2024

II. Knowledge Summary

✨ Core Idea of the Enumeration Method

The Enumeration Method (also known as brute-force search) has the core idea of: exhaustively checking all possible cases, verifying one by one whether each case satisfies the problem's conditions. The enumeration method is the most fundamental and intuitive algorithmic approach. Although it may not always be the most efficient, it can guarantee finding the correct answer for many problems.

✨ Principle of the Enumeration Method

The general problem-solving approach of enumeration is to check whether all candidate answers satisfy the requirements:

1. Find a way to enumerate all possibilities: Determine the enumeration range and enumeration variables
2. Check whether each candidate answer meets the requirements: Verify the conditions for each case

In practice, enumeration is usually implemented through loops. A single loop can enumerate all values of one variable, and multiple nested loops can enumerate combinations of multiple variables. The key when writing an enumeration program is to ensure that all possibilities are enumerated without omission or duplication.

✨ Optimization Techniques for Enumeration

1. Narrow the enumeration range: Carefully analyze the problem conditions to minimize the range that needs to be enumerated. For example, when enumerating factors, you only need to go up to n/2 or even sqrt(n).
2. Early pruning: When you find that a certain case can no longer possibly satisfy the conditions, skip it early. For example, if the sum already exceeds the target value during enumeration, you can directly break.
3. Leverage mathematical properties: For example, for a palindrome number, the hundreds digit equals the units digit, so you can enumerate only the hundreds and tens digits and directly construct the palindrome, rather than enumerating all three-digit numbers and then checking.

✨ Execution Example of the Enumeration Method

Problem: Find the count of all palindrome numbers between 100 and 999. A palindrome number reads the same forwards and backwards.

Analysis: For a three-digit number abc, reading forwards gives abc and reading backwards gives cba. A palindrome requires a==c.

1int count = 0;
2for (int i = 100; i <= 999; i++) {
3    int a = i / 100;       // Hundreds digit
4    int b = (i / 10) % 10; // Tens digit
5    int c = i % 10;        // Units digit
6    if (a == c) {
7        count++;
8    }
9}

Step-by-step execution (partial):

Final result: There are 90 palindrome numbers between 100 and 999.

✨ Complexity Analysis of the Enumeration Method

Time Complexity

The time complexity of the enumeration method depends on the size of the enumeration space:

• Single-level enumeration: O(n)
• Two-level enumeration: O(n²)
• Three-level enumeration: O(n³)
• Enumeration of k variables: O(nᵏ)

Space Complexity

Usually O(1) — the enumeration method generally only needs a few variables to track state and does not require large additional arrays.

Advantages: Simple and intuitive approach, easy to implement, guaranteed to find all solutions. Disadvantages: Inefficient when the enumeration space is too large, which may cause TLE. Pruning or more efficient algorithms are needed for optimization.

✨ Application Scenarios of the Enumeration Method

The enumeration method is suitable for problems that seek feasible solutions, including:

1. Finding a unique solution: The problem has only one correct answer
2. Finding all feasible solutions or their count: Finding all answers that satisfy the conditions
3. Finding the optimal among feasible solutions: Finding the maximum or minimum among all feasible solutions

✨ Detailed Problem-Solving Steps: Perfect Numbers

Problem: Find all perfect numbers between 1 and n. A perfect number is a number that equals the sum of all its proper divisors.

Thought process:

Step 1: Understand the problem. What are proper divisors? They are all divisors of a number except the number itself. For example, the proper divisors of 6 are 1, 2, and 3, and 1+2+3=6, so 6 is a perfect number.

Step 2: Determine the enumeration range. The outer loop enumerates each number i (from 2 to n), and the inner loop enumerates all possible proper divisors j of i (from 1 to i/2).

Step 3: For each number, check whether it is a perfect number. Accumulate the sum of all proper divisors and check whether it equals the original number.

Step 4: Consider optimization. When enumerating divisors, you only need to go from 1 to i/2, because no number greater than i/2 can be a divisor of i (except i itself).

1for (int i = 2; i <= n; i++) {
2    int sum = 0;
3    for (int j = 1; j <= i / 2; j++) { // Only enumerate up to i/2
4        if (i % j == 0) {
5            sum += j;
6        }
7    }
8    if (sum == i) {
9        cout << i << endl;
10    }
11}

✨ Common Mistakes with the Enumeration Method

1. Incomplete enumeration range: Forgetting to include boundary values. For example, the problem says "1 to n", but the loop is written as for(int i=1; i<n; ...), missing n.
2. Redundant enumeration range: Enumerating unnecessary cases, causing duplicate counting or TLE.
3. Incorrect condition checks: For example, using i % j = 0 (assignment) instead of i % j == 0 (comparison) when checking divisors.
4. Reusing loop variables across nested loops: Using the same variable name for both the inner and outer loops, causing logical errors.
5. Ignoring time complexity: The efficiency of enumeration depends on the size of the enumeration space. If the space is too large (e.g., three nested loops each of 10^4), it may cause TLE, and optimization or a different algorithm should be considered.

III. Homework

Programming Exercises

1. Narcissistic Numbers: L2025
2. Dongdong Goes Shopping: L2026