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; } }

在实际教学中，我发现很多初学者最初会倾向于解法二的思路，因为它看起来更"直接"。但通过这个案例的对比分析，学生们能够深刻理解算法选择对性能的影响，以及如何根据问题特点选择最优解法。