Encontrar Pitágoras trio para que a + b + c = 1000

Question

Um trio de Pitágoras é um conjunto de três números naturais, um < b < c, para a qual, um² + b² = c²

Por exemplo, 3² + 4² = 9 + 16 = 25 = 5².

Existe exatamente um trio de Pitágoras, para que a + b + c = 1000.Encontrar o produto abc.

Origem: http://projecteuler.net/index.php?section=problems&id=9

Eu tentei, mas não sabia onde meu código estava errado.Aqui está o meu código em 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

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

explicação:

• b = a;
  Se A, B (a <= B) e C são o trigêmeo pitagórico,
  Então B, a (b> = a) e c - também a solução, para que possamos pesquisar apenas um caso
• c = 1000 - a - b; É uma das condições do problema (não precisamos digitalizar tudo o que é possível 'C': apenas calculá -lo)

Answer 2

Estou com medo ^ não faz o que você acha que faz em C. Sua melhor aposta é usar a*a para quadrados inteiros.

Answer 3

Aqui está uma solução usando a fórmula de Euclides (link).

Vamos fazer alguma matemática: em geral, toda solução terá o formulário

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

onde k, x e y são números inteiros positivos, y <x e gcd (x, y) = 1 (ignoraremos essa condição, o que levará a soluções adicionais. Esses podem ser descartados depois)

Agora, A+B+C = KX²-Ky²+2kxy+Kx²+Ky² = 2kx²+2kxy = 2kx (x+y) = 1000

Divida por 2: kx (x+y) = 500

Agora definimos s = x+y: kxs = 500

Agora estamos procurando soluções de kxs = 500, onde k, x e s são inteiros e x < s < 2x. Como todos eles dividem 500, eles só podem pegar os valores 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Alguns pseudocódigos para fazer isso para n (ele e pode ser feito à mão facilmente para 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

Você ainda pode melhorar isso:

• x nunca será maior que a raiz de N/2
• O loop para s pode começar em x e parar após a aprovação do 2X (se a lista for solicitada)

Para n = 1000, o programa deve verificar seis valores para x e dependendo dos detalhes da implementação até um valor para y. Isso terminará antes de liberar o botão.

Answer 4

Como mencionado acima, ^ é bit xor, não poder.

Você também pode remover o terceiro loop e, em vez disso, usarc = 1000-a-b; e otimize um pouco isso.

Pseudo-código

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

Há uma solução bastante suja, mas rápida, para esse problema. Dadas as duas equações

a*a + b*b = c*c

a+b+c = 1000.

Você pode deduzir a seguinte relação

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

Ou depois de duas transformações matemáticas simples, você recebe:

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

já que um deve ser um número natural. Portanto, você pode:

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

Recebi o resultado 200 e 375.

Boa sorte

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

Não testei isso, mas deve colocá -lo no caminho certo.

Answer 7

A partir de 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,

como você vê, pow está usando a aritmética do ponto flutuante, o que é improvável que você lhe dê o resultado exato (embora neste caso deva ser bom, pois números inteiros relativamente pequenos têm uma representação exata; mas não confie nisso para casos gerais) ... Use n*n Para encaixar os números na aritmética inteira (também, nas CPUs modernas com poderosas unidades de ponto flutuante, a taxa de transferência pode ser ainda maior em ponto flutuante, mas a conversão de um ponto inteiro para flutuante tem um custo muito alto no número de ciclos da CPU; portanto, se você ' estar lidando com números inteiros, tente manter a aritmética inteira).

Algum pseudocódigo para ajudá -lo a otimizar um pouco o seu algoritmo:

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

Em C, o operador calcula Bitwise XOR, não a potência. Usar x*x em vez de.

Answer 9

Como outros mencionaram, você precisa entender o operador. Além disso, seu algoritmo produzirá várias respostas equivalentes com os parâmetros A, B e C em diferentes ordens.

Answer 10

Enquanto tantas pessoas apontaram que seu código funcionará bem quando você mudar para usar pow. Se você estiver interessado em aprender um pouco da teoria matemática como se aplica ao CS, eu recomendaria tentar implementar uma versão mais efiente usando "Fórmula de Euclides" para gerar triplos pitagóricos (link).

Answer 11

Sei que essa pergunta é bastante antiga e todo mundo está postando soluções com 3 para loops, o que não é necessário. Eu resolvi isso em O (n), por **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

Então, resolvendo mais que chegamos;

a+b = 1000-c

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

Se resolvermos mais nós deduzimos para;

a = ((50000- (1000*b))/(1000-b)). Voltamos para "B" e encontramos "A".

Uma vez que temos "A" e "B", obtemos "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;
}

Answer 12

O método Euclides fornece ao perímetro m (m+n) = p/2 onde m> n e os lados são m^2+n^2 é a hipotenusa e as pernas são 2mn e m^2-n^2.Thus m (m+n) = 500 fornece rapidamente m = 20 e n = 5. Os lados são 200, 375 e 425. Use a Euclid para resolver todas as questões primitivas do Pitoro.

Answer 13

Como existem duas equações (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) com três variáveis, nós podemos resolvê-lo em tempo linear por apenas um loop através de todos os valores possíveis de uma variável e, em seguida, nós podemos resolver os outros 2 variáveis em tempo constante.

A partir da primeira fórmula, temos b=1000-a-c, e se substituirmos b na 2ª fórmula com isso, obtemos c^2 = aˆ2 + (1000-a-c)ˆ2, o que simplifica para c=(aˆ2 + 500000 - 1000a)/(1000-a).

Em seguida, temos o loop através de todos os possíveis valores de a, resolver c e b, com as fórmulas acima, e se as condições forem satisfeitas encontramos nosso trio.

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

Answer 14

Eu acho que a melhor abordagem aqui é a seguinte:

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

Explicação: Vamos nos referir à N e uma constante, para que não tenhamos que usar dois loops. Nós podemos fazer isso porquec=n-a-b e b =(a^2-(a-n)^2)/(2(a-n))Eu recebi essas fórmulas resolvendo um sistema de equações:

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

Answer 15

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
}

As respostas acima são boas o suficiente, mas perdendo uma informação importante A + B> C. ;)

Mais detalhes serão fornecidos àqueles que perguntarem.

Answer 16

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)

Otimização adicional da resposta de Oleg. Um lado não pode ser maior que a soma dos outros dois. Portanto, A + B não pode ser inferior a 500.