Оптимальный алгоритм для вычисления пифагорейского триплета

У меня есть это постановка проблемы, где в данном, x^2 + y^2 = c это уравнение, вы должны оптимально найти кортежи (x,y) такое, что уравнение верно.

Учитывая переменную c, значение которой известно, вы должны найти значения (x,y), Так что, если у вас есть c=0, затем x=0 а также y=0, Предположим, у вас есть c=2, затем (x,y) являются (-1,1)(1,-1), (-1,-1), (1,1), Теперь мы должны найти такие значения.

Вам просто нужно посчитать количество таких кортежей для заданного значения c,

Теперь я написал заявление как таковое:

int getCount(int c) {

  int count=0,temp=-1000;

  for(int i=-n;i<n-1;i++) {

    for(int j=-n,j<n;j++) {

      temp= i^2+j^2;

      if(temp==c) {
        count++;
        System.out.println(i+" "+j);
      }
    }
  }
}

Есть ли оптимальный способ сделать это?

Источник

5 ответов

Решение

Если в качестве примера вы увидите, что, получив решение (1,1), все три других легко найти, вам просто нужно изменить знаки или порядок (x,y) (то есть x <-> y),

Теперь вы знаете, что x^2 + y^2 = c Который означает, что x <= sqrt(c) а также y <= sqrt(c), Если вы полагаете, что x <= y тогда у вас есть x <= sqrt(c/2) а также sqrt(c/2) <= y <= sqrt(c),

В самом деле:

  • x^2+x^2 <= x^2 + y^2 = c так x <= sqrt(c/2)
  • x <= y а также y^2 <= x^2 + y^2 = c так sqrt(c/2) <= y <= sqrt(c)

Теперь вы можете легко увидеть, что |sqrt(c)-sqrt(c/2)| < |sqrt(c/2)| для каждого c так что вам просто нужно перечислить все y между sqrt(c/2) а также sqrt(c)вычислить x вокруг него и посмотреть, если x^2+y^2=c,

int print(x,y) {
  System.out.println(x+" "+y);
  System.out.println(-x+" "+y);
  System.out.println(-x+" "+-y);
  System.out.println(x+" "+y);
}

int getCount(int c) {
  if ( (c % 4) == 3)
    return 0;

  int count=0;
  for(int y = Math.sqrt(c/2) ; y <= Math.sqrt() ; y++) {
      int x = (int)Math.sqrt(c-y*y);
      if(x*x + y*y == c){
        count += 4;
        print(x,y);
        if(x != y) {
          count += 4;
          print(y,x);  
        }

      }
  }
}

На примере, если c = 1000*1000 тогда ваше решение будет иметь тест 4n^2 пара (x,y) т.е. если n = sqrt(c), 4*1000*1000 пар.

Тестирование каждого x до sqrt(c) обойдется в 1000 тестов, и мое решение состоит в том, чтобы выполнить только ~300 тестов.

Источник

Создать карту или

{0 => 0, 1 => 1, 4 => 2, 9 => 3, 16 => 4,..., i2 => i}

вектор квадратов

[0, 1, 4, 9, 16,..., i2]

так что (i + 1)2 > c. затем найти все пары значений из контейнера, сумма которых дает c.

Источник

Вы могли бы начать с

if ( (c % 4) == 3)
    return 0;

Каждый квадрат равен 0 или 1 (мод 4), поэтому сумма никогда не может быть 3.

Если c равно 0, 1, 2 (mod 4), пусть ваш кандидат x перейдет от 0 до sqrt(c), вычислит y и посмотрим, является ли оно целым числом. Найдите 3 других решения, изменяя знаки.

Источник

Для тройки Пифагора c^2 = a^2 + b^2 формула Евклида дает нам следующие соотношения, где m и n - произвольная пара натуральных чисел с m> n:

  • а = м ^ 2 - п ^ 2
  • b = 2 * m * n
  • с = м ^ 2 + п ^ 2

Здесь нас интересует поиск m и n с помощью c.

Отношения подразумевают следующее:

c = m^2 + n^2
=> m^2 = c - n^2
=> a = m^2 - n^2 = c - 2.n^2
=> n^2 = (c - a) / 2

С другой стороны:

a^2 + b^2 = c^2
=> b^2 = c^2 - a^2
=> (4.m^2.m^2) = c^2 - a^2
=> m^2 = c^2 - a^2 / 4.n^2
=> m^2 = (c - a)(c + a).2 / 4.(c - a)
=> m^2 = (c + a) / 2

m и n являются целыми числами (не комплексами), следовательно, 0 <= m^2 и 0 <= n^2, следовательно, следующие ограничения для a:

0 <= (c + a) / 2  and 0 <= (c - a) / 2
=> -c <= a <= c

Итак, учитывая c, вы должны перебрать [| -c, c |] (целочисленный диапазон) и вычислить m и n. Заметьте, что здесь мы ищем целые числа, а не действительные числа, поэтому квадратные корни должны приводить к целым числам, следовательно, (c + a) / 2 и (c - a) / 2 тоже должны быть целыми числами, поэтому (c + a) и (c - a) должно быть кратно 2, поэтому a может перебирать диапазон с шагом 2.

  for (int a = -c; a <= c; a += 2) {
      double m2 = (c + a) * 0.5;
      double n2 = (c - a) * 0.5;

      double m_abs = Math.sqrt(m2);
      double n_abs = Math.sqrt(n2);

      if (Math.floor(m_abs) == m_abs &&
              Math.floor(n_abs) == n_abs) {

                      // sqrt(x^2) = abs(x^2) = +/- x
          System.out.println(Double.toString(-m_abs) + ", " + Double.toString(-n_abs));
          System.out.println(Double.toString(-m_abs) + ", " + Double.toString(n_abs));
          System.out.println(Double.toString(m_abs) + ", " + Double.toString(-n_abs));
          System.out.println(Double.toString(m_abs) + ", " + Double.toString(n_abs));
      }
  }
Источник

Я бы сказал, что это дубликат этого вопроса. Вопрос здесь несколько более общий, то есть вопрос не требует, чтобы c был квадратом, но этот вопрос также рассматривается в предыдущих ответах. И вот также хорошее описание факторизации гауссовых целых чисел, которое не полностью описано в другом вопросе.

Источник
Другие вопросы по тегам