海城网站制作建设,长沙市天心区建设局网站,杭州视频网站建设,海宁建设局网站【题目描述】
输出所有形如aabb的4位完全平方数#xff08;即前两位数字相等#xff0c;后两位数字也相等#xff09;。
【解析】
一、问题分析
从问题出发#xff0c;题目要求输出的是满足一定条件的数。数在计算机中是要占存储空间的#xff0c;要在计算机中表示一个…【题目描述】
输出所有形如aabb的4位完全平方数即前两位数字相等后两位数字也相等。
【解析】
一、问题分析
从问题出发题目要求输出的是满足一定条件的数。数在计算机中是要占存储空间的要在计算机中表示一个数一定要考虑它的数据类型、数据长度。这里是4位整数所以用int数据类型就可以了。
如果把数看成一个对象它也有自己的属性和方法。 二、已知条件分析
1. 已知条件转化为隐含条件。
本题对要输出的数给定了3个已知条件
(1) 形如aabb即前两位数字相等后两位数字也相等。注意括号内对aabb的解释只要求前两位相等后两位也相等对ab是否相等未作要求。题目未作要求就是没有限制就是怎样都可以。所以不要看写着形如aabb就想当然地以为a、b要是不同的两个数。a、b只是两个字母是未知数在未给定条件时它可以是任意数。
(2) 4位数。一个数是几位数是从最左侧的第一个非0数开始计算比如0123既不是4位数也不是3位数因为它根本不是数。所以本题要求是4位数a的值不能为0。也就是a的取值范围是1-9b的取值范围是0-9。
(3)完全平方数。完全平方数perfect square指能表示成某个整数的平方的数。例如0、1、4、9都是完全平方数因为它们分别是0、1、2、3的平方。根据定义可知完全平方数是非负整数。
2. 隐含条件转换为数学表达式。
仅仅将已知条件转化为隐含条件还不够还要进一步转化为数学表达式才可能将其转化为代码。
上述三个条件中主要涉及的数学表达式是aabb这个数表示它可以表示成a*1100 b*11
三、算法分析
本题的本质是从一定范围的整数中找出一些符合特殊条件的整数所以可以用“穷举法”。
穷举法的穷举范围极大地影响程序的效率所以要尽量缩小穷举的范围。
本题的穷举范围和符合条件判断有两种
①大范围4位数→缩小范围4位数形如aabb的数无法进一步缩小符合条件完全平方数。
②大范围4位数→缩小范围4位数完全平方数无法进一步缩小符合条件形如aabb
下面分别阐述两种算法。
1. 遍历范围4位形如aabb的数符合条件完全平方数
这个4位数用aabb表示前面讨论过a的取值范围是1-9b的取值范围是0-9。也就是说a取的每一位数字都要与b取的0-9组合一遍就像相亲节目中每个男生都会用目光欻欻歘歘朝着每个女生闪烁一遍。每个男生一个接一个上台轮流闪烁这是一次循环每个男生上台后闪烁对面一个接一个的女生又是一次循环。所以程序要用到循环的嵌套循环里面套循环。
程序主干如下
for(int a 1; a 9; a)for(int b 0; b 9; b)if(aabb是完全平方数) printf(%d\n, aabb);
这段主干程序并不是合法的C程序第三行代码是不符合语法规范的因而无法运行。
这样的不能真正运行的简化代码称为伪代码pseudocode。伪代码主要用于描述算法梗概避开细节启发思路。在使用伪代码时可以不必拘泥格式只求简明即可。
这段伪代码完整地表现出了程序的三个部分遍历、判断、输出。
上述伪代码要变成真正的代码需要解决两个问题
(1) aabb的表示。
C语言中是无法用aabb这样的形式输出数的因为它会被编译器识别为变量。把伪代码改写成代码时一般先选择较为容易的任务来完成。前面讲过这个问题比较简单只要用a*1100 b*11这种表达式的形式表示即可。
(2) 判断aabb是否为完全平方数。
这还不简单吗只要用sqrt()函数给aabb开平方再判断结果是不是一个整数不就行了
这是正向思维这个思路的难点在于sqrt()函数的返回值是double类型这种浮点数是有误差的。这意味着如果它的返回值是0.9999999999它的真实值可能是一个整数1。
所以咱们是不能用下面这种方式来进行判断的
if(sqrt(aabb)最接近sqrt(aabb)的整数)printf(d\n, aabb);
要判断一个浮点数是不是整数只能用一个不太完美的办法求这个浮点数与最接近它的值的整数的差如果这个差小于一个很小的数就认为它是整数。
那这个很小的数应该是多大合适呢
系统为咱们定义了名叫DBL_EPSILON的宏定义在头文件float.h中。它就是那个很小的正数用于处理浮点数精度问题。DBL是double的缩写。EPSILON是希腊语代表第五个希腊字母ε。ε在数学中常被用来表示一个非常小的正数这个数可以任意小但不等于零。
代码如下
#includestdio.h#includemath.h#include float.hint main(){for(int a 1; a 9; a)for(int b 0; b 9; b){int aabb a*1100 b*11; //这里才开始使用n因此在这里定义ndouble r1 sqrt(aabb);int r2 floor(r1 0.5);if(fabs(r1 - r2) DBL_EPSILON) printf(%d\n, aabb);}return 0;}
注意sqrt(aabb)后面加上0.5这个细节这是为了在转化为整数时进行四舍五入。函数floorx返回不超过x的最大整数。这里floor(sqrt(aabb) 0.5)其实也可以写成int r (int)(sqrt(aabb) 0.5)。后者是用数据类型强制转换的方式舍去小数部分。它和用floor函数有什么区别呢读者可以猜想一下。
fabs(x)返回x的绝对值。
虽然用上述代码也能输出正确的结果但不能改变它是个天生残疾的事实。而且如果你忘了或不知道那个很小的数的宏名更当如何呢
换一种思路用逆向思维就能避开浮点数误差找到完美的算法求出最接近sqrt(aabb)的整数反过来判断它的平方是否等于aabb。
代码如下
#includestdio.h#includemath.hint main(){for(int a 1; a 9; a)for(int b 0; b 9; b){int aabb a*1100 b*11; //这里才开始使用n因此在这里定义nint r floor(sqrt(aabb) 0.5);if(r*r aabb) printf(%d\n, aabb);}return 0;}
2. 遍历范围4位完全平方数符合条件形如aabb
这种方法天生具有完美基因因为它不涉及浮点数。
整数开方会产生小数整数的平方只能是整数。
#includestdio.hint main(){for(int x 1; ; x){int aabb x * x;if(aabb 1000) continue;if(aabb 9999) break;int hi aabb / 100;int lo aabb % 100;if(hi/10 hi%10 lo/10 lo%10) printf(%d\n, aabb);}return 0;}
continue和break语句是C语言的两个语句。continue的作用是跳过当前循环体中剩余未执行的语句并立即开始下一次的循环条件判定即执行下一次循环。break的作用是直接跳出循环即立即结束整个循环。
两种算法都介绍完了问题来了哪个算法效率更高呢你猜猜
