9

我刚刚完成了 Project Euler 问题 9（警告剧透）：

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

这是我的解决方案：

public static int specPyth(int num)
{
    for (int a = 1; a < num; a++)
        for (int b = 2; b < a; b++)
            {
                if (a*a +b*b == (num-a-b)*(num-a-b))
                    return a*b*(num-a-b); //ans = 31875000 
            }

    return -1;
}

我不禁想到有一种解决方案只涉及一个循环。有人有想法吗？我更喜欢只使用一个循环的答案，但任何比我目前拥有的更有效的东西都会很好。

4

8 回答 8

22 
if a + b +c = 1000

然后

 a + b + sqroot(a² + b²) = 1000

 -> (a² + b²) = (1000 - a - b)²

 -> a² + b² = 1000000 - 2000*(a+b) + a² + 2*a*b + b²

 -> 0 = 1000000 - 2000*(a+b) + 2*a*b

 -> ... (easy basic maths)

 -> a = (500000 - 1000*b) / (1000 - b)

然后你尝试每一个 b，直到你找到一个从 a 中得到一个自然数。

public static int specPyth(int num)
    {
        double a;
        for (int b = 1; b < num/2; b++)
        {
            a=(num*num/2 - num*b)/(num - b);

            if (a%1 == 0)
                return (int) (a*b*(num-a-b));
        }   

        return -1;
    }

编辑：b 不能高于 499，因为 c>b 和 (b+c) 将高于 1000。

于 2013-06-04T07:45:49.457 回答
5

我强烈建议阅读http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple并编写一个函数来逐个生成毕达哥拉斯三元组。

不想过多剧透，但是这个函数会派上用场来解决许多其他 PE 问题。

（我不认为这种放弃太多，因为 PE 的部分目的是鼓励人们学习这样的东西。）

于 2013-06-05T03:17:17.507 回答
1

首先，由于a是最小的，所以不需要数到num，num/3就足够了，甚至num/(2+sqrt(2))。二、有一个和约束

a+b+c=num
a^2+b^2=c^2

我们可以求解这个方程并找到给定 a 的 b 和 c，它们已经满足这个方程，并且不需要像现在那样检查 a^2+b^2=c^2。您只需要检查 b 和 c 是否为整数。这是在一个循环中完成的

for (int a = 1; a < num/3; a++)
于 2013-06-04T07:48:35.937 回答
1

运行时间为 62 毫秒

    import time
    s = time.time()
    tag,n=True,1000
    for a in xrange (1,n/2):
        if tag==False:
            break
        for b in xrange (1,n/2):
            if a*a + b*b - (n-a-b)*(n-a-b) ==0:
                print a,b,n-a-b
                print a*b*(n-a-b)
                tag=False
    print time.time() - s
于 2014-05-24T18:41:30.813 回答
1

C解

警告：解决方案假定 GCD(a, b) = 1。它在这里有效，但可能并不总是有效。我会在一段时间内修复解决方案。

#include <stdio.h>
#include <math.h>

int main(void)
{
  int n = 1000;         // a + b + c = n
  n /= 2;

  for(int r = (int) sqrt(n / 2); r <= (int) sqrt(n); r++)
  {
    if(n % r == 0)
    {
      int s = (n / r) - r;
      printf("%d %d %d\n", r*r - s*s, 2*r*s, r*r + s*s);
      printf("Product is %d\n", (2*r*s) * (r*r - s*s) * (r*r + s*s));
    }
  }

  return 0;
}

解决方案使用欧几里得三元组公式，该公式指出任何原始三元组的形式为 a = r^2 - s^2, b = 2rs, c = r^2 + s^2。

可以基于 s 为正且 r > s 的事实添加某些限制，例如 sqrt(n / 2) <= r <= sqrt(n)。

警告：如果产品很大，您可能需要 long long

于 2016-12-03T05:03:21.457 回答
0

你说a < b < c，thenb必须总是大于a，所以你在第二个循环中的起点可能是b = a + 1；这肯定会导致更少的迭代。

int specPyth(int num)
{
    for (int a = 1; a < num/3; a++)
        for (int b = a + 1; b < num/2; b++)
        {
            int c = num - a - b;
            if (a * a + b * b == c * c)
                return a * b * c; //ans = 31875000 
        }

    return -1;
}
于 2013-06-04T07:47:27.563 回答
0

绝对不是最佳解决方案，但我的第一反应是使用修改后的 3SUM。在 Python 中，

def problem_9(max_value = 1000):
    i = 0
    range_of_values = [n for n in range(1, max_value + 1)]
    while i < max_value - 3:
        j = i + 1
        k = max_value - 1
        while j < k:
            a = range_of_values[i]
            b = range_of_values[j]
            c = range_of_values[k]
            if ((a + b + c) == 1000) and (a*a + b*b == c*c):
                return a*b*c
            elif (a + b + c) < 1000:
                j += 1
            else:
                k -= 1
        i += 1
    return -1
于 2013-12-01T02:22:57.607 回答
0

在第一个给定的等式中，您有三个变量a, b, c。如果你想找出这个方程的匹配值，你必须运行 3 维循环。幸运的是，还有另一个方程a+b+c=N是N已知数。

使用它，您可以将维度减少到 2，因为如果您知道三个中的两个，则可以计算其余的。例如，如果您知道aand b，则c等于N - a - b。

如果你可以再减少一维循环呢？如果您摆弄两个给定的方程式，这是可能的。拿笔和纸。一旦你得到包含两个变量和一个常数 (N) 的附加方程，你将能够在 中获得结果O(n)。求解a+b+c=n; a^2+b^2=c^2取n和a为常数的两个方程并求解b和c：

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        int n = in.nextInt(); 
        int max=-1;
        int multi=0;
       int b=1,c=1;
        for(int i=1;i<=n;i++)
            {
            if(2*(i-n)!=0)
            b=(2*i*n-(n*n))/(2*(i-n));
            c=n-b-i;
            if( (i*i+b*b==c*c)&& i+b+c==n && b>0 && c>=0 && i+b>c && c+i>b && b+c>i)
                {
                multi=i*b*c;
                if(max<multi)
                    max=multi;

            }
        }
        if(max==-1)
        System.out.println(-1);
        else
            System.out.println(max);

    }
}
于 2016-10-24T19:49:30.423 回答