优化算法来计算勾股三重 [英] Optimum algorithm to calculate pythagorean triplet

问题描述

我有每个人的问题。我有这个问题的声明，其中在给定的， X ^ 2 + Y ^ 2 = C 是方程式，你必须以最佳方式找到元组（X ，Y），使等式成立。

I have a question for everyone. I have this problem statement where in given, x^2 + y^2 = c is the equation, you have to optimally find the tuples (x,y) such that the equation holds true.

给定一个变量C，其值是已知的，你必须要找到的值（X，Y）。因此，假设如果你有 C = 0 ，然后 X = 0 和 Y = 0 。假设你有 C = 2 ，然后（X，Y）是（ - 1， 1） （1，-1），（ - 1，-1）， （1,1）。现在，我们必须找到这些值。

Given a variable c, whose value is known, you have to find the values (x,y). So suppose if you have c=0, then x=0 and y=0. Suppose you have c=2, then (x,y) are (-1,1) (1,-1), (-1,-1), (1,1). Now we have to find such values.

您只需要算这样的元组的数量为℃的给定值。

You just have to count the amount of such tuples for a given value of c.

现在我写的应用程序，例如：

Now I wrote the application as such:

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

有没有最佳的方式做到这一点？

Is there any optimum way to do this?

请让我know.Tanks！

Please let me know.Tanks!

推荐答案

如果您例如，你可以看到，一旦你有解决方案（1,1）三种人很容易找到，你只需要改变的迹象或的顺序（X，Y）。（即X - 其中; - > y）的

If you example you can see that once you have the solution (1,1) all three others are easy to find, you just have to change the signs or the order of (x,y) (ie x <--> y).

现在，你知道， X ^ 2 + Y ^ 2 = C 这意味着 X＆LT; =开方（C）和 Y'LT; =开方（C）。如果假设 X＆LT; = Y 那么你有 X＆LT; =开方（C / 2）和的sqrt（C / 2）＆LT; = Y＆LT; =开方（C）

Now, you know that x^2 + y^2 = c which means that x <= sqrt(c) and y <= sqrt(c). If you suppose that x <= y then you have x <= sqrt(c/2) and sqrt(c/2) <= y <= sqrt(c).

事实上：

• X ^ 2 + X ^ 2'= X ^ 2 + Y ^ 2 = C 让 X＆LT; =开方（C / 2）
• X＆LT; = Y 和 Y ^ 2'= X ^ 2 + Y ^ 2 = C 所以的sqrt（C / 2）＆LT; = Y＆LT; =开方（C）

• x^2+x^2 <= x^2 + y^2 = c so x <= sqrt(c/2)
• x <= y and y^2 <= x^2 + y^2 = c so sqrt(c/2) <= y <= sqrt(c)

现在，你可以很容易地看到 |开方（C）-sqrt（C / 2）| ＆LT; |开方（C / 2）| ，每 C ，所以你只需要枚举所有是的的sqrt（C / 2）和的sqrt（C），计算 X 圆一下，看看是否 X ^ 2 + Y ^ 2 = C 。

Now, you can easily see that |sqrt(c)-sqrt(c/2)| < |sqrt(c/2)| for every c so you just have to enumerate all y between sqrt(c/2) and sqrt(c), compute the x round it and see if 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);  
        }

      }
  }
}

在一个例子，如果ç= 1000 * 1000 那么你的解决方案将有测试 4N ^ 2 夫妇（X，Y）也就是说，如果 N =开方（C），4 * 1000 * 1000的夫妻。

On an example, if c = 1000*1000 then your solution would have test 4n^2 couple (x,y) ie if n = sqrt(c), 4*1000*1000 couples.

测试每x最多的sqrt（三）将花费1000测试，我的解决方案中只是做〜300的测试。

Testing every x up to sqrt(c) would have cost 1000 tests and my solution in only doing ~300 tests.

这篇关于优化算法来计算勾股三重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！