C实战巧用枚举与循环嵌套高效求解四位“aabb”完全平方数在信息学竞赛的入门阶段很多同学会遇到一类经典问题——寻找满足特定条件的数字。今天我们就来探讨一个有趣且富有教学意义的案例如何用C找出所有四位数的aabb型完全平方数。这个题目看似简单却蕴含了编程思维训练的核心要素问题分解、算法选择和代码实现。1. 理解问题本质首先我们需要明确几个关键概念aabb型数字指形如1122、3344这样的四位数其中第1位和第2位数字相同aa第3位和第4位数字也相同bb。例如1111a1, b12233a2, b39999a9, b9完全平方数可以表示为某个整数的平方的数。例如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四位数千位不能为0b十位和个位数字0-9数字构造方法a*1000 a*100 b*10 b这种展开式比字符串拼接更高效例如当a7b4时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×1090次每次循环执行固定数量的算术运算效率极高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; } }在实际教学中我发现很多初学者最初会倾向于解法二的思路因为它看起来更直接。但通过这个案例的对比分析学生们能够深刻理解算法选择对性能的影响以及如何根据问题特点选择最优解法。
C++新手必看：用枚举和循环嵌套，5分钟找出所有四位数的“aabb”完全平方数
C实战巧用枚举与循环嵌套高效求解四位“aabb”完全平方数在信息学竞赛的入门阶段很多同学会遇到一类经典问题——寻找满足特定条件的数字。今天我们就来探讨一个有趣且富有教学意义的案例如何用C找出所有四位数的aabb型完全平方数。这个题目看似简单却蕴含了编程思维训练的核心要素问题分解、算法选择和代码实现。1. 理解问题本质首先我们需要明确几个关键概念aabb型数字指形如1122、3344这样的四位数其中第1位和第2位数字相同aa第3位和第4位数字也相同bb。例如1111a1, b12233a2, b39999a9, b9完全平方数可以表示为某个整数的平方的数。例如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四位数千位不能为0b十位和个位数字0-9数字构造方法a*1000 a*100 b*10 b这种展开式比字符串拼接更高效例如当a7b4时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×1090次每次循环执行固定数量的算术运算效率极高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; } }在实际教学中我发现很多初学者最初会倾向于解法二的思路因为它看起来更直接。但通过这个案例的对比分析学生们能够深刻理解算法选择对性能的影响以及如何根据问题特点选择最优解法。
