Найти пифагорейский триплет, для которого a + b + c = 1000

Question

Пифагорейская тройка - это набор из трех натуральных чисел, a 2 + b ² = c ²

Например, 3 ² + 4 ² = 9 + 16 = 25 = 5 ² .

Существует ровно один пифагорейский триплет, для которого 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();    
}

Answer 1

Как уже упоминали другие, вам нужно понимать оператор ^. Также ваш алгоритм выдаст несколько эквивалентных ответов с параметрами a, b и c в разных порядках.

Answer 2

Поскольку есть два уравнения (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) с тремя переменными, мы можем решить это за линейное время, просто просматривая все возможные значения одной переменной, а затем мы можем решить две другие переменные в константе время.

Из первой формулы мы получаем b=1000-a-c, и если мы заменим b во 2-й формуле на это, мы получим 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;
        }
    }

Answer 3

Метод Евклида дает периметр m (m + n) = p / 2, где m> n и стороны m ^ 2 + n ^ 2 - гипотенуза, ноги - 2mn и m ^ 2-n ^ 2. Таким образом, m (m + n) = 500 быстро дает m = 20 и n = 5. Стороны - 200, 375 и 425. Используйте Евклид, чтобы решить все примитивные вопросы с пирореями.

Answer 4

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.

Answer 5

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 . ;)

Более подробная информация будет предоставлена ​​тем, кто спрашивает.

Answer 6

Я думаю, что лучший подход здесь такой:

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-b и b = (a^2-(a-n)^2)/(2(a-n)) Я получил эти формулы, решив систему уравнений:

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