检查三角形是否正确？

概述我试图检查三角形是否是C语言中的直角三角形. a,b和c是某些三角形的边长. int is_right_triangle(int a, int b, int c){ return (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a);} 如何避免求和和乘法中的整数溢出？假设我们没有很长的 我试图检查三角形是否是C语言中的直角三角形. a,b和c是某些三角形的边长.

int is_right_triangle(int a,int b,int c){    return (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a);}

如何避免求和和乘法中的整数溢出？假设我们没有很长的类型.

解决方法 改进(优化)版本

>找到最大的一面和最小的面. (不失一般性,我们称之为C和A). B是第三方
>现在C2 – A2 = B2为直角三角形.即(C A)*(C-A)= B2,计算unsigned_sum = C A和unsigned_diff = C-A(对于int的总和,保证unsigned int不溢出)
>将sum,diff和B除以sum和diff的gcd.如果它不分B,则它不是直角三角形.如果是这样的话,如果三角形是正确的,则sum和diff将是完美的正方形.
>找到sum和diff的整数平方根.如果根的乘积等于B,则三角形是正确的.

int is_right_triangle(int a,int c){  unsigned int sum,diff;  int f = 2;  /* factor */  unsigned int hcf,irts,irtd;  /* sort */  if(b > c) swap(&b,&c);  if(a > b) swap(&a,&b);  if(b > c) swap(&b,&c);  sum = c;  diff = c;  sum += a;  diff -= a;  hcf = gcd(sum,diff);  if(b % hcf != 0) return 0;  sum /= hcf;  diff /= hcf;  b /= hcf;  irts = isqrt(sum);  if(irts * irts != sum || b % irts != 0) return 0;  b /= irts;  irtd = isqrt(diff);  if(irtd * irtd != diff || b % irtd != 0) return 0;  b /= irtd;  return b == 1;}

您可以找到isqrt @ Methods_of_computing_square_roots的算法或使用二进制搜索方法.

#define NEXT(n,i)  (((n) + (i)/(n)) >> 1)  unsigned int isqrt(int number) {    unsigned int n  = 1;    unsigned int n1 = NEXT(n,number);    while(abs(n1 - n) > 1) {      n  = n1;      n1 = NEXT(n,number);    }    while(n1*n1 > number)      n1--;    return n1;  }

isqrt从codecodex复制而没有变化

老答案

>找到最大的一面和最小的面. (不失一般性,保证unsigned int不溢出)
>收集unsigned_sum和unsigned_diff的主要因子.如果它们不是2的倍数,则不是正确的角度.如果因子是2的倍数,则保持划分copy_of_B = B,一次看到一对素因子. (检查fac * fac< max(unsigned_sum,unsigned_dif),如果fac划分,请尝试与其他划分)
>如果B = 1,则三角形是直角,否则不是.

int is_right_triangle(int a,diff;  int f = 2;  /* factor */  /* sort */  if(b > c) swap(&b,&c);  sum = c;  diff = c;  sum += a;  diff -= a;  while(f * f <= sum || f * f <= diff) {    int count = 0;    while(sum % f == 0) { sum /= f; ++count; }    while(diff % f == 0) { diff /= f; ++count; }    if(count % 2 == 1) return 0;    while(count != 0) {      b /= f;      count -= 2;    }    ++f;  /* f = (f == 2 ? 3 : f + 2); */  }  return b == 1;}

优化
1.如this comment所述,您可以将unsigned_sum,unsigned_diff和b与gcd(unsigned_sum,unsigned_diff)分开,并且可以分别处理unsigned_sum和unsigned_diff.2.在循环中,如果你可以在任何点检查sum和diff的乘积(和b的平方)保证不溢出,你可以检查sum * diff ==(unsigned)b * b并相应地中断.

总结

以上是内存溢出为你收集整理的检查三角形是否正确？全部内容，希望文章能够帮你解决检查三角形是否正确？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。