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 回答
2

因此，如果您仍然需要存储所有四倍数，那么这是新功能，（感谢 Damien）。

只用了1.5 秒。用于查找和存储所有85490。

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

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

               if (d != 0) // a possible Quadruple
               {
                  //System.out.println(Arrays.asList(a, b, c, d));
                  allQuadraples.add(Arrays.asList(a, b, c, d));
                  total++;
               }
            }

      return total;
   }

如果不保存到 中ArrayList，则需要1.3 秒。

于 2020-02-20T18:14:15.820 回答