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

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

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

Метод Евклида дает периметр 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. Используйте Евклид, чтобы решить все примитивные вопросы пирореана.

Я знаю, что этот вопрос довольно старый, и все публиковали решения с 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

Если мы решаем дальше , мы выводим это ;

a = ((50000- (1000 * b)) / (1000-b)). Мы зациклимся на «b» и находим «a».

Как только у нас есть «а» и «б», мы получаем «с».

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

Хотя многие отмечают, что ваш код будет работать нормально, как только вы перейдете к использованию pow. Если вы заинтересованы в изучении математической теории в применении к CS, я бы порекомендовал попробовать реализовать более эффективную версию, используя «формулу Евклида» для генерации пифагорейских троек ( ссылка ).

Из 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 для возведения в квадрат чисел в целочисленной арифметике (также, в современных процессорах с мощными модулями с плавающей запятой пропускная способность может быть даже выше в число с плавающей запятой, но преобразование из целого числа в число с плавающей запятой очень дорого обходится по числу циклов ЦП, поэтому, если вы имеете дело с целыми числами, попробуйте придерживаться целочисленной арифметики).

некоторый псевдокод, чтобы помочь вам немного оптимизировать ваш алгоритм:

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

Существует довольно грязное, но быстрое решение этой проблемы. Учитывая два уравнения

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.

Удачи

Как упомянуто выше, ^ - побитовый 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

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

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

Не тестировал это, но это должно направить вас на верный путь.

В C оператор ^ вычисляет побитовый xor, а не мощность. Вместо него используйте x*x.

Боюсь, что ^ не делает то, что, как вы думаете, делает в C. Лучше всего использовать ] a * a для целых квадратов.

Вот решение, использующее формулу Евклида ( ссылка ).

Давайте подумаем: В общем, каждое решение будет иметь вид

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

где k, x и y - положительные целые числа, y

Теперь 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 . Поскольку все они делят 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