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 关键点解析

1. 枚举范围确定 ：

   • a（千位和百位数字）：1-9（四位数千位不能为0）
   • b（十位和个位数字）：0-9

2. 数字构造方法 ：

   • a*1000 + a*100 + b*10 + b 这种展开式比字符串拼接更高效
   • 例如当a=7，b=4时：7 1000 + 7 100 + 4*10 + 4 = 7000 + 700 + 40 + 4 = 7744

3. 完全平方数验证 ：

   • 使用 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 关键点解析

1. 数字拆分技巧 ：

   • 千位： num / 1000
   • 百位： (num / 100) % 10
   • 十位： (num / 10) % 10
   • 个位： num % 10

2. 模式检查 ：

   • a == b 确保前两位相同
   • c == d 确保后两位相同

3. 性能对比 ：

   • 需要遍历9000个数字（1000-9999）
   • 每个数字都需要进行位数拆分和条件检查
   • 计算量明显大于解法一

3.3 复杂度分析

• 循环次数：9000次（从1000到9999）
• 每次循环需要：
  • 4次除法/取模运算（数字拆分）
  • 2次比较（模式检查）
  • 1次平方根计算（条件满足时）
• 总体计算量远大于解法一

4. 两种解法的比较与选择

4.1 效率对比

指标	解法一（枚举组合）	解法二（数字遍历）
循环次数	90次	9000次
每次循环计算量	较少	较多
适合场景	模式明确的情况	模式复杂的情况

4.2 适用场景分析

• 优先选择解法一 ：

  • 当数字模式明确且可枚举时（如aabb、abab等）
  • 需要处理大量数据时
  • 对性能要求较高的场景

• 考虑解法二 ：

  • 当数字模式复杂，难以直接枚举时
  • 需要同时检查多种数字特征时
  • 代码可读性优先的场景

4.3 扩展思考

在实际编程竞赛中，我们经常会遇到类似的数字特征判断问题。例如：

• 寻找所有"abba"型的素数
• 找出"abcba"型的完全立方数
• 统计满足各位数字之和等于特定值的数字

掌握这两种基本思路后，可以灵活应用到各种变体问题中。关键在于：

1. 准确理解题目要求的数字模式
2. 评估不同解法的计算复杂度
3. 选择最直接高效的实现方式

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

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