эффективный алгоритм для пифагорейских троек в java

Question

Итак, я пытаюсь сделать программу с помощью java. его ввод является целым числом, целые числа рассматриваются как сумма из трех целых чисел a, b и c (a^2 + b^2 = c^2), его выход равен c^2. Для этого я разворачиваю уравнение: a^2 + b^2 - c^2 = 0 и c = sum - a - b, получите . Затем я получаю a + b <= sum*2/3, затем подставляю все комбинации a, b в уравнение, чтобы увидеть, когда оно равно нулю.

Вот мой код:

/** Pythagorean Triples 
    * test case for small numbers 
    * Tony 
    */ 
import java.util.*; 

public class Solution54 { 
    public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 


    int times = sc.nextInt(); 

    for (int i = 0; i < times; i++) { 
     /* prompt the sum and get the equation: 
     * Math.pow(sum, 2) - 24 * (a + b) + 2a*b = 0; 
     * we consider b >= a; 
     */ 
     double sum = sc.nextDouble(); 
     double ablimits = Math.floor(sum/3 * 2); // a + b <= ablimits 
     double alimits = Math.floor(ablimits/2); // a <= alimits 
     //System.out.println("another round"); 
     //System.out.print(alimits + " " + blimits); 
     A: for (double a = 1; a <= alimits; a++) { 
     B: for (double b = a; b <= sum - a; b++) { 
      double result = Math.pow((sum-a-b),2)-a*a-b*b; 
      //System.out.print("when a is " + a + " " + "when b is " + b + ":" + result + ";"); 
      if (Math.pow(sum, 2) - 2 * sum * (a + b) + 2 * a * b == 0) { 
      double answer = a*a + b*b; 
      int output = (int)answer; 
      System.out.print(output + " "); 
      break A; 
      } 
     } 
     } 

    } 
    } 
} 

Когда я вход 1 12, он дает 25 (потому что a,b,c=3,4,5; c^2 = 25), но он не может обрабатывать большие входы, как 14808286, потому что мой алгоритм не является достаточно эффективным. Каков эффективный способ сделать это? Plz!

Answer 1

Позвольте мне предисловие к этому, сказав, что у меня нет интимного знания о пифагорейских троек или математике позади них. Я просто подумал, что это интересная проблема, поэтому я дал ей удар.

Я считаю, что ключом к этой проблеме является знание того, что вы ищете, когда вы просматриваете возможные значения a. Учитывая

a + b + c = sum 

и

a^2 + b^2 = c^2 

вы обнаружите, что

b = (sum/2) * (1 - (a/(sum - a))) 
    = (sum/2) - ((a * sum)/(2 * (sum - a))) 

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

(sum/2) % 1 = 0 

Так что все мы действительно должны проверить, чтобы убедиться, что б справедливо (то есть целое число) является то, что

((a * sum)/(2 * (sum - a))) % 1 = 0 

или, проще говоря,

(a * sum) % (sum - a) = 0 

Некоторые другие ключевые моменты, которые упрощают эту проблему, по крайней мере, как вы заявили:

• Как только у вас есть a, b можно вычислить, используя третье уравнение в этом ответе.
• Как только у вас есть a и b, c легко следует из любого из трех уравнений Пифагора.
• Вам нужно только напечатать c^​​2 как ваш выход. Как только это будет сделано, вы можете сломаться.

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

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 

    // Get the sum from System.in. 
    int sum = sc.nextInt(); 

    // If the given sum is odd, return immediately. 
    // No Pythagorean triple will have an odd sum. 
    if ((sum^1) == 1) { 
     return; 
    } 

    // Try all values of a within the expected bounds. 
    int aBound = sum/2; 
    for (int a = 1; a < aBound; a++) { 
     // Check whether b would be a whole number with this value of a. 
     if ((a * sum) % (a - sum) == 0) { 
      int b = (sum * (2 * a - sum))/(2 * a - 2 * sum); 
      int c = sum - a - b; 
      System.out.println((int)Math.pow(c, 2)); 
      break; 
     } 
    } 
} 

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

Надеюсь, это поможет!