What is Enumeration AlgorithmThe Enumeration Algorithm, also known as the brute force algorithm, is one of the most intuitive problem-solving methods in computer science. Its core idea is very simple:Systematically traverse all possible solutions, checking each candidate solution one by one to see if it meets the problem’s conditions, until the correct solution is found or all possibilities have been exhausted.During today’s physical education class,the PE teacher selected team members for the basketball team based on the criterion ofheight exceeding 1.5 meters. The teacher arranged a group of children in a line, measuring their heights one by one and filtering them.This process of measuring and filtering each student within the examination range is the enumeration process.
Steps of the Enumeration Algorithm
Implementing the enumeration algorithm in C++ typically follows these steps:
-
Determine the range of the solution space
-
Construct loops (traverse all possible cases)
-
Perform conditional checks for each possibility
-
Output or save the solutions that meet the conditions
This “brute force” method, while seemingly simple and crude, is often the most reliable and easy-to-implement solution in many scenarios.
Characteristics of the Enumeration Algorithm
Advantages:
Simple and straightforward (direct)): The algorithm logic is simple and clear (example + conditional checks), making it easy to understand and implement.
Guaranteed correctness: As long as the solution space contains the correct answer, enumeration will definitely find it.
Strong universality: Applicable to various types of problems, especially when there are no better algorithms available.
Disadvantages:
Low efficiency: Requires checking all possibilities, often resulting in high time complexity.
High resource consumption: For large-scale problems, it may consume excessive time and memory.
Not suitable for large-scale problems: When the solution space is too large, it becomes practically infeasible.
Examples
Example 1: Find all prime numbers under 100
Problem breakdown:
1) Determine the range of candidate solutions. Every number from 2 to 100 is a suspect target.
2) Construct loops. Set the loop variable i, starting from 2 and ending at 100, incrementing by 1 each iteration to ensure every value is covered.
3) In the loop, check if each candidate value is prime.
4) If the result of step 3 is true, then output it.
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
cout << "Prime numbers under 100 are:" << endl;
for (int num = 2; num <= 100; num++) {
if (isPrime(num)) {
cout << num << " ";
}
}
return 0;
}Example 2: Narcissistic number problem
A three-digit narcissistic number is a three-digit number whose sum of the cubes of its digits equals the number itself. Output all three-digit narcissistic numbers.
Problem breakdown:
1) Determine the candidate range. Three-digit narcissistic numbers are found among three-digit numbers, so the range is 100 to 999.
2) Construct loops. Set the loop variable i, starting from 100 to 999, incrementing by 1 each time.
3) In the loop, check if the current i value is a narcissistic number (separate the digits into hundreds, tens, and units).
4) Output the numbers that meet the judgment conditions.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
cout << "Three-digit narcissistic numbers are:" << endl;
for (int num = 100; num < 1000; num++) {
int a = num / 100; // Hundreds
int b = (num / 10) % 10; // Tens
int c = num % 10; // Units
if (a*a*a + b*b*b + c*c*c == num) {
cout << num << endl;
}
}
return 0;
}Example 3: The chicken and rabbit in the same cage problem
Given that there are 35 heads and 94 feet in the cage, find out how many chickens and rabbits there are.
Problem breakdown:
1) Determine the candidate range.
The range for chickens is [0, 35], and the maximum range for rabbits is also [0, 35].
2) Construct loops.
To output two solutions, we define two variables i for the number of chickens and j for the number of rabbits. Both i and j start at 0 and have a maximum value of 35.
3) Determine the judgment conditions.
There are 35 heads and 94 feet.
i + j == 35 && 2*i + 4*j == 94
4) Output the number of chickens and rabbits that meet the judgment conditions.
#include <bits/stdc++.h>
using namespace std;
int main(){
int head, foot;
cin >> head >> foot;
for(int i=0; i<=head; i++) {
for(int j=0; j<=head; j++) {
if(i+j==head && 2*i + 4*j==foot) {
cout << "Number of chickens=" << i << " Number of rabbits=" << j << endl;
}
}
}
return 0;
}Optimization of the chicken and rabbit in the same cage problem
Problem breakdown:
Once we define the number of chickens, the number of rabbits can be directly represented as heads – chickens, so there is no need to enumerate the number of rabbits anymore.
#include <iostream>
using namespace std;
int main() {
int heads = 35;
int feet = 94;
for (int chicken = 0; chicken <= heads; chicken++) {
int rabbit = heads - chicken;
if (2 * chicken + 4 * rabbit == feet) {
cout << "Chickens: " << chicken << " Rabbits: " << rabbit << endl;
break;
}
}
return 0;
}Example 4: My house number
Luogu B2133
https://www.luogu.com.cn/problem/B2133?contestId=269808
I live in a short alley, and the house numbers in this alley start from 1 and are numbered sequentially.
If the sum of the house numbers of the other houses minus twice my house number equalsn (the only input of the problem), find my house number and the total number of houses. The data guarantees a unique solution.
Problem breakdown:
1) Currently, we only know one input integer n. Try to construct the formula for n⬇️
n == sum of all house numbers – 3 * my house number
2) To find my house number, we can clearly use enumeration. Enumerate the total number of house numbers (x) and my house number (y). The judgment condition becomes⬇️
n == x * (x + 1) / 2 – 3 * y
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i=1; i<=10000; i++) {
int sum = i*(i+1)/2;
for(int j=1; j<=i; j++) {
if(sum-3*j==n) {
cout << j << " " << i;
break;
}
}
}
return 0;
}Example 5: Sum and product of primes
Luogu B2134
https://www.luogu.com.cn/problem/B2134?contestId=269808
Input a positive integer not exceeding 10000, representing the sum of two primes. Find the maximum product of these two primes.
Problem breakdown:
This problem is clearly an enumeration thought process.
Use i and j to represent the two primes, with the judgment condition being i + j == s && i is prime && j is prime.
#include <bits/stdc++.h>
using namespace std;
bool isprime(int a) {
bool flag = true;
for(int i=2; i*i<=a; i++) {
if(a%i==0) {
flag = false;
break;
}
}
return flag;
}
int main(){
int n;
cin >> n;
int multi = 1;
for(int i=2; i<=n-2; i++) {
int e = n - i;
if(isprime(i) && isprime(e)) {
multi = max(multi, i*e);
}
}
cout << multi;
return 0;
}Conclusion
The enumeration algorithm is an important foundational algorithm in C++ programming, reflecting the original and powerful capabilities of computers—fast computation and traversal. Although it may not be efficient in certain cases, the enumeration algorithm has the following values:
-
Thinking training: Helps beginners establish algorithmic thinking and logical reasoning abilities.
-
Problem analysis: As a starting point for problem-solving, it often provides ideas for further optimization.
-
Practical application: In cases of small data scale or high correctness requirements, enumeration is the best choice.
-
Verification tool: Can be used to verify the correctness of other complex algorithms.
In actual programming, we should choose appropriate algorithms based on the problem scale and requirements. For small-scale problems, the enumeration algorithm is simple and effective; for large-scale problems, more efficient algorithms need to be considered. Mastering the enumeration algorithm is a fundamental skill for every C++ programmer, laying a solid foundation for solving more complex problems.
Follow the Informatics Assistant for economical and practical C++ introductory solutions. If you want to learn C++, you can leave a message on the public account or contact the Informatics Assistant.
Join my Luogu team for free, learn, communicate, and spar together.https://www.luogu.com.cn/team/108017
Author profile: Master’s degree from Huazhong University of Science and Technology, former Huawei engineer, currently a teacher of algorithm courses in big data at a university. Committed to making learning simpler.