C++新手必看：用枚举和循环嵌套，5分钟找出所有四位数的“aabb”完全平方数
C++实战：巧用枚举与循环嵌套高效求解四位“aabb”完全平方数
在信息学竞赛的入门阶段，很多同学会遇到一类经典问题——寻找满足特定条件的数字。今天我们就来探讨一个有趣且富有教学意义的案例：如何用C++找出所有四位数的"aabb"型完全平方数。这个题目看似简单，却蕴含了编程思维训练的核心要素：问题分解、算法选择和代码实现。
1. 理解问题本质
首先我们需要明确几个关键概念：
aabb型数字：指形如"1122"、"3344"这样的四位数，其中第1位和第2位数字相同（aa），第3位和第4位数字也相同（bb）。例如：
- 1111（a=1, b=1）
- 2233（a=2, b=3）
- 9999（a=9, b=9）
完全平方数：可以表示为某个整数的平方的数。例如：
- 16 = 4²
- 121 = 11²
- 7744 = 88²
我们的目标是找出所有同时满足这两个条件的四位数。这类问题在信息学奥赛(NOI)和编程初学者练习中非常常见，它能有效训练我们的枚举思维和代码实现能力。
2. 解法一：枚举数字组合法
2.1 算法思路
最直观的解法是直接枚举所有可能的a和b组合，然后构造对应的aabb型数字，最后验证它是否是完全平方数。这种方法思路清晰，实现简单，特别适合初学者理解。
#include <iostream> #include <cmath> using namespace std; int main() { for(int a = 1; a <= 9; a++) { // 千位数不能为0 for(int b = 0; b <= 9; b++) { // 个位数可以为0 int num = a * 1000 + a * 100 + b * 10 + b; int root = sqrt(num); if(root * root == num) { cout << num << endl; } } } return 0; }2.2 关键点解析
枚举范围确定：
- a（千位和百位数字）：1-9（四位数千位不能为0）
- b（十位和个位数字）：0-9
数字构造方法：
a*1000 + a*100 + b*10 + b这种展开式比字符串拼接更高效- 例如当a=7，b=4时：71000 + 7100 + 4*10 + 4 = 7000 + 700 + 40 + 4 = 7744
完全平方数验证：
- 使用
sqrt()函数获取平方根整数部分 - 通过
root * root == num验证是否为完全平方数
- 使用
注意：直接比较浮点数可能存在精度问题，这里通过整数运算避免了这个问题。
2.3 复杂度分析
- 外层循环：9次（a从1到9）
- 内层循环：10次（b从0到9）
- 总循环次数：9×10=90次
- 每次循环执行固定数量的算术运算，效率极高
3. 解法二：数字遍历拆分法
3.1 算法思路
另一种思路是遍历所有四位数（1000-9999），对每个数字进行位数拆分，检查是否符合aabb模式，再验证是否是完全平方数。
#include <iostream> #include <cmath> using namespace std; int main() { for(int num = 1000; num <= 9999; num++) { int a = num / 1000; // 千位 int b = (num / 100) % 10; // 百位 int c = (num / 10) % 10; // 十位 int d = num % 10; // 个位 if(a == b && c == d) { // 检查aabb模式 int root = sqrt(num); if(root * root == num) { cout << num << endl; } } } return 0; }3.2 关键点解析
数字拆分技巧：
- 千位：
num / 1000 - 百位：
(num / 100) % 10 - 十位：
(num / 10) % 10 - 个位：
num % 10
- 千位：
模式检查：
a == b确保前两位相同c == d确保后两位相同
性能对比：
- 需要遍历9000个数字（1000-9999）
- 每个数字都需要进行位数拆分和条件检查
- 计算量明显大于解法一
3.3 复杂度分析
- 循环次数：9000次（从1000到9999）
- 每次循环需要：
- 4次除法/取模运算（数字拆分）
- 2次比较（模式检查）
- 1次平方根计算（条件满足时）
- 总体计算量远大于解法一
4. 两种解法的比较与选择
4.1 效率对比
| 指标 | 解法一（枚举组合） | 解法二（数字遍历） |
|---|---|---|
| 循环次数 | 90次 | 9000次 |
| 每次循环计算量 | 较少 | 较多 |
| 适合场景 | 模式明确的情况 | 模式复杂的情况 |
4.2 适用场景分析
优先选择解法一：
- 当数字模式明确且可枚举时（如aabb、abab等）
- 需要处理大量数据时
- 对性能要求较高的场景
考虑解法二：
- 当数字模式复杂，难以直接枚举时
- 需要同时检查多种数字特征时
- 代码可读性优先的场景
4.3 扩展思考
在实际编程竞赛中，我们经常会遇到类似的数字特征判断问题。例如：
- 寻找所有"abba"型的素数
- 找出"abcba"型的完全立方数
- 统计满足各位数字之和等于特定值的数字
掌握这两种基本思路后，可以灵活应用到各种变体问题中。关键在于：
- 准确理解题目要求的数字模式
- 评估不同解法的计算复杂度
- 选择最直接高效的实现方式
5. 代码优化与进阶技巧
5.1 预计算平方数
我们可以预先计算所有四位完全平方数，然后检查它们是否符合aabb模式：
#include <iostream> using namespace std; int main() { for(int root = 32; root <= 99; root++) { // 32²=1024, 99²=9801 int num = root * root; int a = num / 1000; int b = (num / 100) % 10; int c = (num / 10) % 10; int d = num % 10; if(a == b && c == d) { cout << num << endl; } } return 0; }这种方法的循环次数更少（仅68次），效率更高。
5.2 数学优化
观察aabb型数字的结构：
num = 1100×a + 11×b = 11×(100a + b)
因为num是完全平方数，且含有因数11，所以100a + b必须是11×k²的形式。利用这个数学性质可以进一步优化算法。
5.3 性能测试对比
我们通过简单的时钟计数来比较三种方法的性能：
#include <iostream> #include <ctime> using namespace std; void method1() { /* 解法一代码 */ } void method2() { /* 解法二代码 */ } void method3() { /* 预计算代码 */ } int main() { clock_t start = clock(); method1(); clock_t end = clock(); cout << "Method 1: " << (end-start) << " clocks" << endl; start = clock(); method2(); end = clock(); cout << "Method 2: " << (end-start) << " clocks" << endl; start = clock(); method3(); end = clock(); cout << "Method 3: " << (end-start) << " clocks" << endl; return 0; }典型测试结果可能如下：
- 解法一：约200时钟周期
- 解法二：约15000时钟周期
- 预计算方法：约100时钟周期
6. 实际应用与变体问题
掌握了这个案例的精髓后，我们可以解决许多类似的编程问题。例如：
6.1 找出所有三位"aba"型完全平方数
for(int a = 1; a <= 9; a++) { for(int b = 0; b <= 9; b++) { int num = a*100 + b*10 + a; int root = sqrt(num); if(root * root == num) { cout << num << endl; } } }6.2 寻找"abab"型完全立方数
for(int a = 1; a <= 9; a++) { for(int b = 0; b <= 9; b++) { int num = a*1000 + b*100 + a*10 + b; int root = cbrt(num); // 立方根函数 if(root * root * root == num) { cout << num << endl; } } }6.3 统计特殊数字组合
比如统计所有四位数中，各位数字的平方和等于该数字本身的数：
for(int num = 1000; num <= 9999; num++) { int a = num / 1000; int b = (num / 100) % 10; int c = (num / 10) % 10; int d = num % 10; if(a*a + b*b + c*c + d*d == num) { cout << num << endl; } }在实际教学中，我发现很多初学者最初会倾向于解法二的思路，因为它看起来更"直接"。但通过这个案例的对比分析，学生们能够深刻理解算法选择对性能的影响，以及如何根据问题特点选择最优解法。