我试图检查三角形是否是C语言中的直角三角形. a,b和c是某些三角形的边长.
@H_
403_2@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,则三角形是正确的.
@H_
403_2@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的算法或使用二进制搜索方法.
@H_
403_2@#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,则三角形是直角,否则不是.
@H_
403_2@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并相应地中断.
