找到毕达哥拉斯三元组,其中a + b + c = 1000

Question

毕达哥拉斯三元组是一组三个自然数,a <b <c,其中,² + b ² = c ²

例如,3 ² + 4 ² = 9 + 16 = 25 = 5 ².

恰好存在一个毕达哥拉斯三元组,其中a + b + c = 1000.找到产品abc.

资料来源:http://projecteuler.net/index.php？section = problem&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();    
}

Answer 1

我担心^你不会做你认为它在C中做的事情.你最好的选择是使用a*a整数方块.

Answer 2

#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':只计算它)

Answer 3

这是使用Euclid公式(链接)的解决方案.

让我们做一些数学:一般来说,每个解决方案都有形式

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的一个值.这将在您释放按钮之前终止.

Answer 4

如上所述,^是按位xor,而不是幂.

您也可以删除第三个循环,而是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

Answer 5

对这个问题有一个非常肮脏但快速的解决方案.鉴于这两个方程式

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.

祝好运

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

没有测试过这个,但它应该让你走在正确的轨道上.

Answer 7

来自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

Answer 8

在C中,^运算符计算按位xor,而不是幂.请x*x改用.