求100以内的勾股数 - 李臣的博客

作者在 2010-07-05 21:15:59 发布以下内容

近日在论坛看到一则帖子说是求100以内的勾股数，给出代码如下：

#include "stdio.h"
int YES_NO (int *a,int n ,int q);
int YES_NO (int a[],int n,int q){
   int i;
   for (i=0;i<n;i++){
      if(a[i]==q) {return 0;break;}
   }
   return 1;
}

int main(){
   long int p,q,m,i,n=0;
   int a[100];

   for(m=1;m<100;m++){
       for(p=1;p<100;p++){
           for(q=1;q<100;q++){
              if(m*m==p*p+q*q){
                 a[n]=p;
                 if (YES_NO(a,n,q)) {
                       n++;
                       printf("%ld*%ld+%ld*%ld=%ld*%ld\n",p,p,q,q,m,m);
                 }

              }

           }
       }
   }

getch();

}

我感觉这段代码还可以优化一下以提高效率，在DEVc++下调试通过代码如下：

#include <stdio.h>
#include <stdlib.h>
int jo(int a,int b,int c);
int j_o(int a);

int j_o(int a)/*判断a是否是偶数*/
{if(a/2==0)
return 0;
else return 1;
    }

int jo(int a,int b,int c)/*判断a+b=c是否满足：奇+偶=奇，奇+奇=偶,偶+偶=偶的关系*/
{
    if(j_o(c)==j_o(j_o(a)+j_o(b)))
    return 1;
    else return 0;
    }

int main(){
   long int p,q,m;

   for(m=1;m<100;m++){
       for(p=m;p<100;p++){
           for(q=p+1;q<((p+q)<100?(p+q):100);q++){
          if(jo(m,p,q)){
              if(q*q==p*p+m*m){
                  printf("%ld*%ld+%ld*%ld=%ld*%ld\n",m,m,p,p,q,q);
                }
              }
           }
       }
   }
    system("pause");
}

代码解释如下：

源代码中的主函数中用三层循环，但我感觉时间复杂度太大，有些m,p,q组合根本就构不成三角形，所以可以提前就把它们从循环中剔除，设此直角三角形的三边为a,b,c(其中c为斜边，a<b)。

则三边应满足

a-b<c<a+b,

c>max(a,b)

所以斜边c满足max(a,b)<c<min((a+b),100)。

又由奇数的平方是奇数，偶数的平方是偶数可知，a*a,b*b,c*c需满足奇+偶=奇，奇+奇=偶,偶+偶=偶这三个关系，所以用函数jo(int a,int b,int c)来判断a,b,c是否满足上述关系，但是我感觉如果是在小整数之内求勾股数优势不明显。