求毕达哥拉斯三元组，其中 a + b + c = 1000

StackOverflow https://stackoverflow.com/questions/2817848

题

毕达哥拉斯的三胞胎是三个自然数，a <b <c，为此2 + b2 =c2

例如，32 + 42 = 9 + 16 = 25 = 52.

恰好存在一个毕达哥拉斯三元组，其中 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();    
}
有帮助吗？

解决方案 

#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;
    如果 a、b (a <= b) 和 c 是毕达哥拉斯三元组，
    那么 b、a (b >= a) 和 c - 也是解决方案，因此我们只能搜索一种情况
  • c = 1000 - a - b；这是问题的条件之一（我们不需要扫描所有可能的“c”：计算一下即可）

其他提示

恐怕^不会做你认为它在C.你最好的办法是使用a*a整数平方。

这是使用欧几里得公式的解决方案（关联).

让我们做一些数学计算：一般来说，每个解决方案都具有以下形式

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，程序必须检查 6 个 x 值，并根据实现细节最多检查 1 个 y 值。这将在您释放按钮之前终止。

如上所述，^是逐位异或，而不是功率。

您还可以去除第三环，而是使用 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

有一个很肮脏的，但快速的解决这个问题。给出的两个等式

A * A + B * B = C * C

A + B + C = 1000。

可以推导出以下关系

α=（1000 * 1000-2000 * B）/（2000-2b）

或经过两次简单的数学变换，您可以：

α= 1000 *（500-B）/（1000 - b）中

由于必须是自然数。因此可以：

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

GOT导致200和375。

好运

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

没有测试过这一点，但它应该设置你在正确的轨道上。

从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使用浮点运算，这是不可能给你确切的结果（尽管在这种情况下，应该OK，因为相对小的整数有一个精确的表示，但不依赖于一般例）...使用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

在C中的^运算符计算按位异或，而不是功率。使用x*x代替。

正如其他人所说，你需要了解^运算符。 也您的算法将产生多个等效的答案与所述参数a，b和c在不同的订单。

虽然很多人都指出你的代码将正常工作，一旦你切换到使用pow。如果您有兴趣了解一点数学理论，因为它适用于CS，我会建议您尝试，以实现使用“欧几里得的公式”更EFFIENT版本生成勾股数（的链接）。

我知道这个问题是很老了，每个人都已经张贴的解决方案与3圈，这是没有必要的。我这解决了为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

如果我们进一步解决的我们的推导它;

  

α=（（50000-（1000 * B））/（1000-B））。    我们环路“B”，并找到“一”。

     

一旦我们有 “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;
}

欧几里得方法给出了周长为m（M + N）= P / 2，其中m> n和侧面平方公尺+ N ^ 2是斜边和腿的2mn和平方公尺正^ 2.thus m个（m + N）= 500很快给出M = 20和n = 5。侧面是200，375和425使用欧几里得解决所有pythorean原始的问题。

由于有两个方程（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)。

然后，我们通过的所有可能值循环，解决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;
        }
    }

我觉得这里最好的办法是这样的：

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和恒定的，所以我们不会有使用两个循环。 我们可以这样做是因为 c=n-a-b且b = (a^2-(a-n)^2)/(2(a-n)) 我通过求解方程系统得到了这些公式：

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

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 即可。 ;）

的更多细节将被提供给那些谁问。

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)

这Oleg的答案进一步优化。 一方不能比其他两个的总和。 所以A + B不能小于500

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top