30

毕达哥拉斯三元组是三个自然数的集合，a < b < c，其中，a 2 + b 2 = c 2

例如，3 2 + 4 2 = 9 + 16 = 25 = 5 2。

恰好存在一个毕达哥拉斯三元组，其 a + b + c = 1000。求积 abc。

来源：http ://projecteuler.net/index.php?section=problems&id=9

我试过但不知道我的代码哪里出错了。这是我在 C 中的代码：

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


void main()
{
    int a=0, b=0, c=0;
    int i;
    for (a = 0; a<=1000; a++)
    {
        for (b = 0; b<=1000; b++)
        {
            for (c = 0; c<=1000; c++)
            {
                if ((a^(2) + b^(2) == c^(2)) && ((a+b+c) ==1000)))
                    printf("a=%d, b=%d, c=%d",a,b,c);
            }
        }
    }
getch();    
}
4

16 回答 16

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

int main()
{
    const int sum = 1000;
    int a;
    for (a = 1; a <= sum/3; a++)
    {
        int b;
        for (b = a + 1; b <= sum/2; b++)
        {
            int c = sum - a - b;
            if ( a*a + b*b == c*c )
               printf("a=%d, b=%d, c=%d\n",a,b,c);
        }
    }
    return 0;
}

解释：

  • b = 一个；
    如果 a, b (a <= b) 和 c 是毕达哥拉斯三元组，
    那么 b, a (b >= a) 和 c - 也是解，所以我们只能搜索一种情况
  • c = 1000 - a - b; 这是问题的条件之一（我们不需要扫描所有可能的'c'：只需计算它）
于 2010-05-12T12:32:09.160 回答
31

恐怕^不会像您在 C 中认为的那样做。最好的选择是使用a*a整数平方。

于 2010-05-12T10:26:20.920 回答
18

这是使用欧几里得公式（链接）的解决方案。

让我们做一些数学运算：通常，每个解决方案都有以下形式

a=k(x²-y²)
b=2kxy
c=k(x²+y²)

其中 k、x 和 y 是正整数，y < x 并且 gcd(x,y)=1 （我们将忽略这个条件，这将导致额外的解决方案。这些可以在之后丢弃）

现在，a+b+c= kx²-ky²+2kxy+kx²+ky²=2kx²+2kxy = 2kx(x+y) = 1000

除以 2：kx(x+y) = 500

现在我们设置 s=x+y: kxs = 500

现在我们正在寻找 kxs=500 的解，其中 k、x 和 s 是整数并且x < s < 2x。由于它们都除以 500，它们只能取值 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500。一些伪代码可以对任意 n（它和可以是n=1000 时用手轻松完成）

If n is odd
  return "no solution"
else
  L = List of divisors of n/2
for x in L
  for s in L
    if x< s <2*x and n/2 is divisible by x*s
      y=s-x
      k=((n/2)/x)/s      
      add (k*(x*x-y*y),2*k*x*y,k*(x*x+y*y)) to list of solutions
sort the triples in the list of solutions
delete solutions appearing twice
return list of solutions

您仍然可以改进这一点：

  • x 永远不会大于 n/2 的根
  • s 的循环可以从 x 开始并在通过 2x 后停止（如果列表是有序的）

对于 n = 1000，程序必须检查 x 的六个值，并根据实现的细节检查 y 的一个值。这将在您释放按钮之前终止。

于 2010-05-14T14:49:06.193 回答
15

如上所述，^ 是按位异或，而不是幂。

您也可以删除第三个循环，而是使用 c = 1000-a-b;和优化它一点。

伪代码

for a in 1..1000
    for b in a+1..1000
        c=1000-a-b
        print a, b, c if a*a+b*b=c*c
于 2010-05-12T10:28:21.417 回答
13

这个问题有一个非常肮脏但快速的解决方案。给定两个方程

a*a + b*b = c*c

a+b+c = 1000。

可以推导出以下关系

a = (1000*1000-2000*b)/(2000-2b)

或者经过两次简单的数学转换，你会得到：

a = 1000*(500-b) / (1000 - b)

因为 a 必须是自然数。因此，您可以：

for b in range(1, 500):
    if 1000*(500-b) % (1000-b) == 0:
        print b, 1000*(500-b) / (1000-b)

得到结果 200 和 375。

祝你好运

于 2010-08-08T21:33:52.327 回答
6 
#include <stdio.h>

int main() // main always returns int!
{
 int a, b, c;
 for (a = 0; a<=1000; a++)
 {
  for (b = a + 1; b<=1000; b++) // no point starting from 0, otherwise you'll just try the same solution more than once. The condition says a < b < c.
  {
   for (c = b + 1; c<=1000; c++) // same, this ensures a < b < c.
   {
    if (((a*a + b*b == c*c) && ((a+b+c) ==1000))) // ^ is the bitwise xor operator, use multiplication for squaring
     printf("a=%d, b=%d, c=%d",a,b,c);
   }
  }
 }
 return 0;
}

尚未对此进行测试，但它应该使您走上正轨。

于 2010-05-12T10:29:15.360 回答
6

来自man pow：

POW(3)                                       Linux Programmer's Manual                                      POW(3)

NAME
       pow, powf, powl - power functions

SYNOPSIS
       #include <math.h>

       double pow(double x, double y);
       float powf(float x, float y);
       long double powl(long double x, long double y);

       Link with -lm.

   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

       powf(), powl(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99

DESCRIPTION
       The pow() function returns the value of x raised to the power of y.

RETURN VALUE
       On success, these functions return the value of x to the power of y.

       If  x  is  a  finite  value less than 0, and y is a finite non-integer, a domain error occurs, and a NaN is
       returned.

       If the result overflows, a range error occurs, and the functions return HUGE_VAL, HUGE_VALF, or  HUGE_VALL,

如您所见，pow正在使用浮点运算，这不太可能给您确切的结果（尽管在这种情况下应该没问题，因为相对较小的整数具有精确的表示形式；但对于一般情况不要依赖它）.. . 用于n*n对整数运算中的数字进行平方（同样，在具有强大浮点单元的现代 CPU 中，浮点的吞吐量甚至更高，但是从整数转换为浮点在 CPU 周期数上的成本非常高，所以如果您正在处理整数，请尝试使用整数算术）。

一些伪代码可以帮助您稍微优化您的算法：

for a from 1 to 998:
    for b from 1 to 999-a:
        c = 1000 - a - b
        if a*a + b*b == c*c:
             print a, b, c
于 2010-05-12T10:40:09.800 回答
5

在 C 中，^ 运算符计算按位异或，而不是幂。改为使用x*x。

于 2010-05-12T10:25:22.093 回答
3

我知道这个问题已经很老了，每个人都在发布带有 3 个 for 循环的解决方案，这不是必需的。我在 O(n) 中解决了这个问题，通过**equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

因此，我们得到进一步解决；

a+b = 1000-c

(a+b)^2 = (1000-c)^2

如果我们进一步求解，我们将其推断为；

a=((50000-(1000*b))/(1000-b))。我们循环寻找“b”，然后找到“a”。

一旦我们有了“a”和“b”，我们就会得到“c”。

public long pythagorasTriplet(){
    long a = 0, b=0 , c=0;

    for(long divisor=1; divisor<1000; divisor++){
        if( ((500000-(1000*divisor))%(1000-divisor)) ==0){
            a = (500000 - (1000*divisor))/(1000-divisor);
            b = divisor;
            c = (long)Math.sqrt(a*a + b*b);
            System.out.println("a is " + a + " b is: " + b + " c is : " + c);
            break;
        }
    }
    return a*b*c;
}
于 2013-07-18T14:14:06.603 回答
2

正如其他人所提到的，您需要了解 ^ 运算符。此外，您的算法将产生多个等效答案，其中参数 a、b 和 c 以不同的顺序排列。

于 2010-05-12T10:29:45.110 回答
2

尽管许多人指出，一旦您切换到使用pow. 如果您有兴趣学习一些适用于 CS 的数学理论，我建议您尝试使用“欧几里德公式”来实现更有效的版本，以生成毕达哥拉斯三元组（链接）。

于 2010-05-14T05:51:37.567 回答
1

欧几里德方法给出周长为 m(m+n)= p/2 其中 m> n 并且边是 m^2+n^2 是斜边并且腿是 2mn 并且 m^2-n^2.thus m(m+n)=500 很快给出 m=20 和 n=5。边是 200、375 和 425。使用 Euclid 解决所有 pythorean 原始问题。

于 2014-04-13T18:35:14.240 回答
1

由于有两个具有三个变量的方程（a+b+c = 1000&& aˆ2 + bˆ2 = cˆ2），我们可以通过遍历一个变量的所有可能值在线性时间内求解它，然后我们可以在恒定时间内求解其他 2 个变量。

从第一个公式，我们得到b=1000-a-c，如果我们用这个替换第二个公式中的 b，我们得到c^2 = aˆ2 + (1000-a-c)ˆ2，它简化为c=(aˆ2 + 500000 - 1000a)/(1000-a)。

然后我们遍历 a 的所有可能值，用上面的公式求解 c 和 b，如果满足条件，我们就找到了我们的三元组。

    int n = 1000;

    for (int a = 1; a < n; a++) {
        int c = (a*a + 500000 - 1000*a) / (1000 - a);
        int b = (1000 - a - c);

        if (b > a && c > b && (a * a + b * b) == c * c) {
            return a * b * c;
        }
    }
于 2017-06-01T12:02:58.253 回答
0

我认为这里最好的方法是：

int n = 1000;
unsigned long long b =0;
unsigned long long c =0;
for(int a =1;a<n/3;a++){
    b=((a*a)- (a-n)*(a-n)) /(2*(a-n));
    c=n-a-b;

    if(a*a+b*b==c*c)
        cout<<a<<' '<<b<<' '<<c<<endl;
 }

解释：我们将参考 N 和 A 常数，因此我们不必使用两个循环。我们可以这样做，因为 c=n-a-bb=(a^2-(a-n)^2)/(2(a-n)) 我通过求解方程组得到了这些公式：

a+b+c=n, a^2+b^2=c^2

于 2016-08-02T09:16:02.170 回答
0 
func maxProd(sum:Int)->Int{
    var prod = 0
    //    var b = 0
    var c = 0
    let bMin:Int = (sum/4)+1 //b can not be less than sum/4+1 as (a+b) must be greater than c as there will be no triangle if this condition is false and any pythagorus numbers can be represented by a triangle.
    for b in bMin..<sum/2 {
        for a in ((sum/2) - b + 1)..<sum/3{ //as (a+b)>c for a valid triangle
            c = sum - a - b
            let csquare = Int(pow(Double(a), 2) + pow(Double(b), 2))
            if(c*c == csquare){
                let newProd = a*b*c
                if(newProd > prod){
                    prod = newProd
                    print(a,b,c)
                }
            }
        }
    }
    //
    return prod
}

上面的答案已经足够好了，但是缺少一条重要的信息a + b > c。;)

更多细节将提供给询问的人。

于 2016-09-19T09:20:35.303 回答
0 
for a in range(1,334):
    for b in range(500, a, -1):
        if a + b < 500:
            break
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a,b,c)

奥列格的回答进一步优化。一侧不能大于其他两侧之和。所以 a + b 不能小于 500。

于 2018-10-16T03:27:28.150 回答