1

そこでJavaを使ってプログラムを作ってみました。その入力は整数で、整数は 3 つの整数 a、b、および c ( a^2 + b^2 = c^2) の合計と見なされ、その出力は c^2 です。これを行うには、式を展開して、結合a^2 + b^2 - c^2 = 0してc = sum - a - b、取得しMath.pow(sum, 2) - 2 * sum * (a + b) + 2 * a * bます。次にa + b <= sum*2/3、a、b のすべての組み合わせを方程式に代入して、いつゼロになるかを確認します。

これが私のコードです：

/** Pythagorean Triples
  * test case for small numbers
  * Tony
  */
import java.util.*;

public class Solution54 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);


    int times = sc.nextInt();

    for (int i = 0; i < times; i++) {
      /* prompt the sum and get the equation:
       * Math.pow(sum, 2) - 24 * (a + b) + 2a*b = 0;
       * we consider b >= a;
       */
      double sum = sc.nextDouble();
      double ablimits = Math.floor(sum / 3 * 2); // a + b <= ablimits
      double alimits = Math.floor(ablimits / 2); // a <= alimits
      //System.out.println("another round");
      //System.out.print(alimits + " " + blimits);
      A: for (double a = 1; a <= alimits; a++) {
        B: for (double b = a; b <= sum - a; b++) {
          double result = Math.pow((sum-a-b),2)-a*a-b*b;
          //System.out.print("when a is " + a + " " + "when b is " + b + ":" + result + ";");
          if (Math.pow(sum, 2) - 2 * sum * (a + b) + 2 * a * b == 0) {
            double answer = a*a + b*b;
            int output = (int)answer;
            System.out.print(output + " ");
            break A;
          }
        }
      }

    }
  }
}

を入力する1 12と 25 が返されますが (なぜなら)、アルゴリズムが十分に効率的でないため、a,b,c=3,4,5; c^2 = 25大きな入力を処理できません。14808286これを行う効率的な方法は何ですか？どうぞ！

4

1 に答える 1

1

私はピタゴラス数やその背後にある数学についての詳細な知識を持っていないと言って、これを前置きさせてください. これは面白い問題だと思ったので、試してみました。

この問題の鍵は、a の可能な値をスキャンするときに探しているものを知ることだと思います。与えられた

a + b + c = sum

と

a^2 + b^2 = c^2

あなたはそれを見つけるでしょう

b = (sum / 2) * (1 - (a / (sum - a)))
  = (sum / 2) - ((a * sum) / (2 * (sum - a)))

b は整数でなければならないことがわかります。ピタゴラス数の興味深い特性は、和が常に偶数になることです。つまり、

(sum / 2) % 1 = 0

したがって、b が有効 (つまり整数) であることを確認するために実際に確認する必要があるのは、

((a * sum) / (2 * (sum - a))) % 1 = 0

または、もっと簡単に言えば、

(a * sum) % (sum - a) = 0

少なくともあなたが述べたように、この問題を単純化する他のいくつかの重要なポイント:

  • a を取得したら、この回答の 3 番目の式を使用して b を計算できます。
  • a と b が分かれば、c はピタゴラスの三重方程式のいずれかから簡単に導き出されます。
  • 出力として c^2 を印刷するだけです。これが完了したら、あなたは壊れることができます。

コードは非常に単純になります。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // Get the sum from System.in.
    int sum = sc.nextInt();

    // If the given sum is odd, return immediately.
    // No Pythagorean triple will have an odd sum.
    if ((sum ^ 1) == 1) {
        return;
    }

    // Try all values of a within the expected bounds.
    int aBound = sum / 2;
    for (int a = 1; a < aBound; a++) {
        // Check whether b would be a whole number with this value of a.
        if ((a * sum) % (a - sum) == 0) {
            int b = (sum * (2 * a - sum)) / (2 * a - 2 * sum);
            int c = sum - a - b;
            System.out.println((int)Math.pow(c, 2));
            break;
        }
    }
}

私はピタゴラスのトリプルについて数学的に深く理解していないので、 a のどの値を実際にチェックする必要があるかを決定する際に、さらに最適化を行うことができる可能性が非常に高いことに注意してください。それにはいくつかの数学的基準があると思います。

これが役立つことを願っています！

于 2016-10-13T03:44:05.377 に答える