-2

有一个三角形，它的斜边长度是给我们的。现在我们的任务是找出其他两侧是否也是整数。

对于上述问题，我构建了一个代码，但效率低下，您能否建议任何有效的算法。

我的工作

#include<stdio.h>
#include<cmath>

using namespace std;

int isInt(double x) {
    if( (x - (int)x) == 0 ) return 1;
    return 0;
}

main() {
    int S;
    int flag = 0;

    scanf("%d", &S);
    flag = 0;
    for(int i = 1; i < S; i++) {
       if( isInt(sqrt(S*S - i*i)) ) {
           printf("EXIST\n");
           flag = 1;
           break;
        }
    }
    if(!flag) printf("NOT EXIST\n");
    return 0;
}
4

1 回答 1

0

如果我对您的理解正确，您正在尝试回答“是否存在带有斜边 S 的整数大小的直角三角形？”。

立即改进您的方法：

  • 将 i 从 1 循环到 S/2，而不是从 1 循环到 S-1。
    • 实际上，S/2 本身也不是必需的，因为这意味着 a==b，因此 c 必须包含奇数个 sqrt(2) 因子。
  • （无需设置 flag=0 两次。）

您可以使用这种仅整数变体，而不是检查整数平方根（sqrt 操作很耗时）：

int check(int c){
  int a=1;
  int b=c-1;
  int cc=c*c;
  while(a<b){
    int sum=a*a+b*b;
    if(sum==cc) return true;
    if(sum<cc){
      a++;
    }else{
      b--;
    }
  }
  return false;
}

（代码未经测试。）

还有其他方法可以回答涉及可表达性定理的问题，即应用于给定假设的平方的两个平方和。但是，这些通常涉及分解，这也是一个难题。

（编辑：删除了关于分解复杂性的错误陈述）

更多信息：

http://en.wikipedia.org/wiki/Pythagorean_triple http://en.wikipedia.org/wiki/Fermat 's_theorem_on_sums_of_two_squares

（见评论，我不允许发布足够多的链接）

于 2013-10-17T09:52:26.777 回答