检查三角形是否正确？

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)*(C-A)=B²，计算 unsigned_sum=C+A 和 unsigned_diff=C-A(对于 int 的总和，unsigned int 保证不会溢出)
3. 将 sum、diff 和 B 除以 sum 和 diff 的 gcd。如果它不能分割 B，则它不是直角三角形。如果是这样，如果三角形是正确的，则 sum 和 diff 将是完美的正方形。
4. 求和与差的整数平方根。如果根的乘积等于 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)*(C-A)=B²，计算 unsigned_sum=C+A 和 unsigned_diff=C-A(对于 int 的总和，unsigned 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.如this comment所述, 你可以用 gcd(unsigned_sum, unsigned_diff) 划分 unsigned_sum, unsigned_diff 和 b 并且可以分别处理 unsigned_sum 和 unsigned_diff。
2. 在循环中，如果您可以随时检查 sum 和 diff(以及 b 的平方)的乘积是否保证不会溢出，您可以检查 sum * diff == (unsigned)b * b 并相应地中断。