1. 问题分析与算法设计
这个编程题目要求我们找出101到n之间所有满足两个条件的三位数：1)是完全平方数；2)有两位数字相同。我们先来分析问题的核心要点。
完全平方数是指可以表示为某个整数的平方的数，比如121是11的平方（11×11=121）。题目中限定了三位数的范围，所以平方根的范围应该在11到31之间（因为10²=100，31²=961，32²=1024已经超出三位数范围）。
判断数字是否有两位相同，我们可以分解数字的各位：百位、十位和个位。具体来说：
- 百位数字：num/100
- 十位数字：(num/10)%10
- 个位数字：num%10
然后比较这三个数字中是否有任意两个相等即可。
2. 代码实现与解析
2.1 主函数设计
主函数负责处理输入输出，调用核心计算函数：
c复制#include<stdio.h>
#include<math.h>
int sq(int n); // 函数声明
int main() {
int n;
scanf("%d", &n); // 读取用户输入的n值
printf("101~%d之间是完全平方数并且有两位数相同的整数有%d个\n", n, sq(n));
return 0;
}
注意：在实际应用中，应该添加输入验证，确保n是三位数且大于101。这里为了专注于核心算法，我们省略了这部分代码。
2.2 核心计算函数实现
c复制int sq(int n) {
int num, i, count;
count = 0; // 计数器初始化
// 遍历可能的平方根
for(i = 11; i <= (int)sqrt(n); i++) {
num = pow(i, 2); // 计算平方数
// 检查是否有两位数字相同
if((num%10) == (num/100) || // 个位等于百位
(num%10) == ((num/10)%10) || // 个位等于十位
(num/100) == ((num/10)%10)) { // 百位等于十位
count++;
}
}
return count;
}
2.3 代码解析
-
循环范围确定：
- 从i=11开始，因为10²=100不满足>101的条件
- 上限是(int)sqrt(n)，这是为了确保我们只计算到n的平方根
-
数字分解与比较：
num%10获取个位数(num/10)%10获取十位数num/100获取百位数- 通过三个条件判断是否有任意两位相等
-
类型转换：
- 使用(int)sqrt(n)将平方根转换为整数，避免浮点数比较问题
3. 算法优化与改进
3.1 性能优化
当前算法的时间复杂度已经是O(√n)，相当高效。但我们可以做一些微优化：
-
避免重复计算：
- 将
num/100和(num/10)%10的计算结果存储到临时变量中
- 将
-
使用乘法代替pow函数：
num = i * i比pow(i, 2)更高效
优化后的代码：
c复制int sq(int n) {
int num, i, count, a, b, c;
count = 0;
for(i = 11; i <= (int)sqrt(n); i++) {
num = i * i;
a = num / 100; // 百位
b = (num / 10) % 10; // 十位
c = num % 10; // 个位
if(a == b || a == c || b == c) {
count++;
}
}
return count;
}
3.2 功能扩展
如果需要输出所有符合条件的数字，可以修改函数如下：
c复制int sq(int n) {
int num, i, count, a, b, c;
count = 0;
printf("符合条件的数字有：\n");
for(i = 11; i <= (int)sqrt(n); i++) {
num = i * i;
a = num / 100;
b = (num / 10) % 10;
c = num % 10;
if(a == b || a == c || b == c) {
printf("%d ", num);
count++;
}
}
printf("\n");
return count;
}
4. 测试用例与验证
4.1 测试用例设计
为了验证程序的正确性，我们应该设计多个测试用例：
-
边界测试：
- 输入120（最小有效输入）
- 输入999（最大三位数）
-
典型测试：
- 输入500（中间值）
- 输入400（包含多个符合条件的数）
-
特殊测试：
- 输入101（刚好等于下限）
- 输入100（无效输入，应该处理但当前代码未处理）
4.2 预期结果
根据数学计算，101-999之间的完全平方数有：
11²=121, 12²=144, ..., 31²=961
其中有两位数相同的包括：
121, 144, 225, 400, 441, 484, 676, 900
共8个，与样例输出一致。
5. 常见问题与调试技巧
5.1 常见问题
-
输入验证缺失：
- 当前代码没有验证n是否为三位数
- 解决方案：添加输入验证代码
-
浮点数精度问题：
- 使用sqrt()函数可能引入浮点数精度问题
- 解决方案：使用整数运算或添加小的epsilon值
-
数字分解错误：
- 在分解数字时可能出错，特别是十位数的计算
- 解决方案：仔细检查分解逻辑
5.2 调试技巧
-
打印中间结果：
- 在循环中添加打印语句，检查每个步骤的计算结果
-
单元测试：
- 为数字分解和比较逻辑编写独立的测试函数
-
使用调试器：
- 在IDE中使用调试器逐步执行代码，观察变量变化
6. 完整代码实现
以下是包含输入验证的完整代码：
c复制#include<stdio.h>
#include<math.h>
int sq(int n);
int main() {
int n;
printf("请输入一个三位数n(101<=n<=999): ");
scanf("%d", &n);
if(n < 101 || n > 999) {
printf("输入无效，请输入101-999之间的三位数\n");
return 1;
}
printf("101~%d之间是完全平方数并且有两位数相同的整数有%d个\n", n, sq(n));
return 0;
}
int sq(int n) {
int num, i, count, a, b, c;
count = 0;
for(i = 11; i <= (int)sqrt(n); i++) {
num = i * i;
a = num / 100;
b = (num / 10) % 10;
c = num % 10;
if(a == b || a == c || b == c) {
count++;
}
}
return count;
}
7. 扩展思考
7.1 算法通用化
这个算法可以推广到其他位数的情况。例如，找出所有四位数中满足条件的数：
- 调整平方根范围（32到99）
- 修改数字分解逻辑（需要分解千位数）
7.2 数学性质分析
观察这些数字，我们可以发现一些有趣的数学性质：
- 这些数字都是完全平方数
- 它们的数字排列有对称性（如121、484等是回文数）
- 这类数字在密码学和校验码中有应用
7.3 性能对比
我们可以比较不同实现方式的性能：
-
预计算法：
- 预先计算所有符合条件的数，存储在一个数组中
- 查询时只需统计范围内的数
-
位运算法：
- 使用位运算来比较数字是否相同
在实际测试中，当前算法已经足够高效，对于三位数范围不需要过度优化。