检查三角形是否正确？

Question

我试图检查三角形是否是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);
}

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

Answer 1

改进（优化）版本

1. 找出最大的边和最小的边。（不失一般性，我们将它们称为 C 和 A）。B 是第三边
2. 现在 C ² - A ² = B ²为直角三角形。即 (C+A)*(CA)=B ²，计算 unsigned_sum=C+A 和 unsigned_diff=CA （保证 unsigned int 的和不会溢出int）
3. 将 sum、diff 和 B 除以 sum 和 diff 的 gcd。如果它不能整除B，则它不是直角三角形。如果是的话，如果三角形是正确的，那么 sum 和 diff 将是完全平方数。
4. 求 sum 和 diff 的整数平方根。如果根的乘积等于B，则三角形是直角三角形。

int is_right_triangle(int a, int b, 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直接复制过来，没有任何改变}

旧答案

1. 找出最大的边和最小的边。（不失一般性，我们将它们称为 C 和 A）。B 是第三边
2. 现在 C ² - A ² = B ²为直角三角形。即 (C+A)*(CA)=B ²，计算 unsigned_sum=C+A 和 unsigned_diff=CA （保证 unsigned int 的和不会溢出int）
3. 收集 unsigned_sum 和 unsigned_diff 的质因数。如果它们不是 2 的倍数，则不是直角。如果因数是 2 的倍数，则继续除 copy_of_B = B，一次看到一对质因数。（检查 fac*fac < max(unsigned_sum, unsigned_dif)，如果 fac 整除其中一个，也尝试与其他整除）
4. 如果最后 B = 1，则三角形是直角，否则不是。

int is_right_triangle(int a, int b, int c)
{
  unsigned int sum, diff;
  int f = 2;  /* factor */

  /* 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;

  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. 正如此评论中提到的，您可以用 gcd(unsigned_sum, unsigned_diff) 除 unsigned_sum、unsigned_diff 和 b，并且可以分别处理 unsigned_sum 和 unsigned_diff。
2. 在循环中，如果您可以在任何点检查sum和diff（以及 b 的平方）的乘积保证不会溢出，您可以进行sum * diff == (unsigned)b * b相应的检查和中断。