2

私はすべてのピタゴラスの四重奏を取得しようとしています:

a^2 + b^2 + c^2 = d^2 when a, b, c <= 1000、

私のコードはそれらすべてを生成します ( 85490) が、約10 分かかります。

実行時間を短縮しようとしています。どうすれば実行時間を改善できますか? 任意の提案をお願いします。

これが私のコードです。

   static int isSquare(int n)
   {
      int m = (int) Math.sqrt(n);

      return m * m == n ? m : 0;
   }

   static List<List<Integer>> allQuadraples = new ArrayList<>();

   static int findQuadraples(int range)
   {
      int total = 0;

      for (int a = 1; a <= range; a++)
         for (int b = 1; b <= range; b++)
            for (int c = 1; c <= range; c++)
            {
               int sum = a * a + b * b + c * c;

               int d = isSquare(sum);

               if (d != 0) // a possible Quadruple
               {
                  List<Integer> oneQuadraple = new ArrayList<>(Arrays.asList(a, b, c, d));
                  Collections.sort(oneQuadraple); // sorting before insertion for comparing later
                  if (!allQuadraples.contains(oneQuadraple))
                  {
                     System.out.println(oneQuadraple);
                     allQuadraples.add(oneQuadraple);
                     total++;
                  }
               }
            }

      return total;
   }
4

2 に答える 2

2

これは、遅い言語での別のアプローチです。と一致することa^2 + b^2ですd^2 - c^2。操作は遅くなりますが、アルゴリズムO(n^2)はO(n^3).

Python では、ラップトップで 1.3 秒未満かかりました。

#! /usr/bin/env python3
limit = 1000

square_differences = {}
for c in range(limit, 0, -1):
    for d in range (c+1, 2*c):
        diff = d*d - c*c
        if 3*limit*limit< diff:
            break
        elif diff not in square_differences:
            square_differences[diff] = []
        square_differences[diff].append((c, d))

quads = []
for a in range(1, limit+1):
    for b in range(a, limit+1):
        s = a*a + b*b
        if s in square_differences:
            for c, d in square_differences[s]:
                if c < b:
                    break
                else:
                    quads.append((a, b, c, d))

print(len(quads))
于 2020-02-20T19:06:54.373 に答える