勾股数元组 （C语言代码）
这一题的关键是，尽量减少循环层数。那就要根据数学关系，先尽可能地缩小变量的取值范围。
首先题目中有a < b < c;
2ab < a^2 + b^2 = c^2 <=M^2，推出b<M^2/(2*a) && b<M 。
2*a^2 < a^2 + b^2 = c^2 <=M^2, 推出a < (M/2)^0.5 && a < b 。
#include <stdio.h>
#include <stdlib.h>/*标准库头文件*/
#include <string.h>
#include <math.h>
int isHZ(int n1, int n2)/*判断两数是否互质*/
{
int min , max;
if(n1> n2)
{
min = n2;
max = n1;
}
else
{
min = n1;
max = n2;
}
if(min == 1) return 0;/*1本身非质非合，不与任何数互质*/
int i;
for(i=min;i>1;i--)/*从较小的那一个数开始往下找公约数*/
{
if(min%i == 0 && max%i == 0) return 0;
}
return 1;
}
int isHZ_3N(int n1, int n2, int n3)/*判断3个数是否两两互质*/
{
if(isHZ(n1, n2) && isHZ(n1, n3) && isHZ(n2, n3))
return 1;
return 0;
}
int isPFS(int n)/*判断一个数是否为某个整数的平方*/
{
double q = sqrt( (double) n);
int n2 = (int) q;
if( q == n2 ) return 1;
return 0;
}
int main(void)
{
int N, M;
scanf("%d%d", &N, &M);
int i, j, k, num = 0;
if(N == 1) N = 2;
for(i=N;i < M/sqrt(2);i++)
{
for(j=i+1;j<(M*M/i/2) && j<M;j++)
{
int l = i*i+j*j;
if(isPFS(l) && l <= M*M )
{
k = (int) sqrt(l);
if(isHZ_3N(i, j, k))
{
printf("%d %d %d\n", i, j, k);
num ++;
}
}
}
}
if(!num)
{
printf("NA");
}
return 0；
}
#C语言编程题##OD机试题##勾股数元组#
查看3道真题和解析
投递华为等公司10个岗位