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

Question

У меня есть эта постановка задачи, где в данном случае 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); 
     } 
    } 
    } 
} 

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

Answer 1

Если вы, например, видите, что если у вас есть решение (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 тестов.

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

• = т^2 - п^2
• Ь = 2 * т * п
• с = т^2 + п^2

Здесь мы заинтересованы в поиске м и н с с.

The отношений означает следующее:

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 

м и п представляют собой целые числа (не комплексы), следовательно, 0 < = т^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) и (с - а) должно быть кратно 2, поэтому можно перебрать диапазон на шаге 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)); 
     } 
    } 

Answer 5

Я бы сказал, что это дубликат this question. Вопрос здесь несколько более общий, т. Е. Вопрос не требует, чтобы с был квадратом, но это также рассматривается в предыдущих ответах. И здесь также a nice description of the factorization of Gaussian integers, что не полностью описано в другом вопросе.