-2

三角形があり、その斜辺の長さが与えられます。ここでのタスクは、他の 2 つの辺も整数かどうかを調べることです。

上記の質問に対して、私は 1 つのコードを作成しましたが、それは非効率的です。同じための効率的なアルゴリズムを提案できますか?

私の仕事

#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-1 ではなく、1 から S/2 にループします。
    • 実際には、S/2 自体も必要ありません。これは a==b を意味するため、c には奇数の sqrt(2)-factor が含まれている必要があります。
  • (flag=0 を 2 回設定する必要はありません。)

整数の平方根 (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;
}

(コードはテストされていません。)

与えられた仮説の 2 乗に適用される 2 つの 2 乗の和としての表現可能性の定理を含む質問に答える方法は他にもあります。ただし、これらには一般的に因数分解が含まれており、これも難しい問題です。

(編集:因数分解の複雑さに関する誤った記述を削除)

詳細情報:

http://en.wikipedia.org/wiki/Pythagorean_triple http://en.wikipedia.org/wiki/フェルマーの s_theorem_on_sums_of_two_squares

（コメントを参照してください。十分なリンクを投稿することは許可されていません）

于 2013-10-17T09:52:26.777 に答える