java 中勾股三元组的高效算法

Question

所以我尝试使用java制作一个程序。它的输入是整数，整数被认为是 3 个整数 a、b 和 c (a^2 + b^2 = c^2) 的总和，它的输出是 c^2。为此，我展开方程组合 a^2 + b^2 - c^2 = 0 和 c = sum - a - b，得到 Math.pow(sum, 2) - 2 * sum * (a + b) + 2 * 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 这样的大输入，因为我的算法不够高效。这样做的有效方法是什么？请！

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)))

你知道b必须是整数。毕达哥拉斯三元组的一个有趣属性是它们的和总是偶数。也就是说

(sum / 2) % 1 = 0

所以我们真正需要检查以确保 b 有效（即整数）的是

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

值得注意的是，由于我对毕达哥拉斯三元组缺乏深入的数学理解，因此在决定实际需要检查 a 的哪些值时，很可能可以进行一些进一步的优化。我想这有一些数学标准。

希望对您有所帮助！

java 中勾股三元组的高效算法

efficient algorithm for Pythagorean Triples in java

java

algorithm

pythagorean