首页 > 编程语言 > 详细

算法 之 aabb

时间:2018-01-14 00:39:48      阅读:116      评论:0      收藏:0      [点我收藏+]

标签:highlight   一起   -h   实际应用   tro   相等   pos   技术   color   

题目描述输出所有形如aabb4位完全平方数(即前两位数字相等,后两位数字也相等)

分支和循环结合在一起时功能强大:

下面列举所有可能的结果aabb,然后判断它们是否为完全平方数。注意a的范围是1~9,但b可以是0.                                  

1  for(int a=1;a<=9;a++)
2      for(int b=0;b<=9;b++)
3         If(aabb是完全平方数)
4                printf(“%d\n”,aabb);                       

        上面的程序并不完整——“aabb是完全平方数”是中文描述,而不是合法的C语言表达式,而aabb在C语言中也是另外一个变量,而不是把两个数字a和b拼在一起。这个把这样“不是真正程序”的“代码”成为伪代码(pseudocode)。虽然有一些正规的伪代码的定义,但在实际应用中,并不需要太拘泥于为代码的格式。主要的目标是描述算法梗概,避开细节,启发思路。

        写出伪代码之后,我们需要考虑如何把它变成真正的代码。上面的伪代码有两个“非法”的地方;完全平方数判定,以及aabb这个变量。后者相对比较容易;用另外一个变量n=a×1100+b×11存储即可。

接下来的问题就要困难一些了:如何判断n是否为完全平方数?

方法一:PS(floor(x),也写做Floor(x),其功能是“向下取整”,或者说“向下舍入”,即取不大于x的最大整数)

 1 #include<stdio.h>  
 2 #include<math.h>  
 3 int main()  
 4 {  
 5    for(int a=1;a<=9;a++)  
 6       for(int b=0;b<=9;b++)  
 7       {  
 8        int n=a*1100+b*11;//这里开始使用n,因此在这里定义n  
 9        int m=floor(sqrt(n)+0.5); 
10        if(m*m==n)  
11         printf("%d\n",n);  
12       }  
13    return 0;  
14 }  

         可不可以这样写?If(sqrt(n)==floor(sqrt(n))) printf(“%d\n”,n);即直接判断sqrt(n)是否为整数。理论上当然没问题,但这样写不保险,因为浮点数的运算(和函数)有可能存在误差。假设在经过大量计算后,由于误差的影响,整数1变成了0.99999999,floor的结果会是0而不是1,。为了减少误差的影响,一般改成四舍五入,即floor(x+0.5)。如果难以理解,可以想象在数轴上把一个单位区间左移0.5个单元的距离。

Floor(x)等于1的区间为【1,2】,而floor(x+0.5)等于1的区间为【0.5,1.5】.

  浮点运算可能存在误差。再进行浮点运算比较时,应考虑到浮点误差。

  总结:小数部分为0.5的数也会受到浮点误差的影响,因此任何一道严密的算法竞赛题目都需要想办法解决这个问题

另一思路是枚举平方根x,从而避免开方操作。

#include<stdio.h>  
int main()  
{  
   for(int x=1;;x++)     //for循环没有指定循环条件  如果期待你从32开始可以不用判断1000
   {  
      int n=x*x;  
    if(n<1000) continue;
if(n>9999) break; int high=n/100; int low=n%100; if(high/10==high%10&&low/10==low%10) printf("%d\n",n); } return 0; }

答案为技术分享图片

 

.

算法 之 aabb

标签:highlight   一起   -h   实际应用   tro   相等   pos   技术   color   

原文:https://www.cnblogs.com/lzhh/p/acm_n0.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号