Найти все пифагорейские четверки быстрее, когда a, b или c <= 1000 - PullRequest
Новая
       42

Найти все пифагорейские четверки быстрее, когда a, b или c <= 1000

2 голосов
/ 20 февраля 2020

Я пытаюсь получить все пифагорейские четверки:

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;
   }

Ответы [ 2 ]

2 голосов
/ 20 февраля 2020

Вот другой подход на более медленном языке. Что должно соответствовать a^2 + b^2 с d^2 - c^2. Операции идут медленнее, но алгоритм O(n^2), а не O(n^3).

В Python это заняло <1,3 секунды на моем ноутбуке. </p> 

#! /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))
2 голосов
/ 20 февраля 2020

Итак, если вам все еще нужно хранить все четверки, то это новая функция, ( Благодаря Дэмиену ).

Потребовалось только 1,5 сек c . для поиска и хранения всего 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 se c.

...