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

Ответ 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;
}

объяснение:

•  
• b = a;    если a, b (a <= b)) и c - пифагорейский триплет,
     то b, a (b >= a) и c - также решение, поэтому мы можем искать только один случай  
• c = 1000 - a -b;    это одно из условий проблемы (не нужно сканировать все возможные "c": просто вычислите его)

Ответ 2

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

Ответ 3

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

Сделаем некоторую математику: В общем случае каждое решение будет иметь вид

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. Это прекратится, прежде чем вы отпустите кнопку.

Ответ 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

Ответ 5

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

aa + bb = 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.

Удачи.

Ответ 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;
}

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

Ответ 7

От man pow:

POW(3)                                       Linux Programmer 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, поэтому, если вы имеете дело с целыми числами, попробуйте придерживаться целочисленной арифметики).

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

Ответ 11

Я знаю, что этот вопрос довольно старый, и все выставляют решения с 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 * б))/(1000 б)).  Мы зацикливаем на "b" и находим "a".

Как только у нас есть "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;
}

Ответ 12

в С# он отлично работает) Однако, конечно, это не лучший способ для вычисления))

using System.Text;
 using System.Threading.Tasks;

  namespace ConsoleApplication3
  {
    class Program
{
    static void Main(string[] args)
    {

    double sum;
        double  vv=1000;

       for (int i = 1; i <1001; i++)
       {
           for (int j = 1; j < 1001; j++)
           {
                for (int k = 1; k < 1001; k++)
                {

                    if ((Math.Pow(i, 2) == Math.Pow(j, 2) + Math.Pow(k, 2)) && i+j+k == 1000) {
                        Console.WriteLine(i + " " + j + " " + k + " = "+(i*j*k));
                        Console.ReadKey();
                    }

                }
           }
       }



    }
}

}

Ответ 13

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

Ответ 14

Вот мой код в javascript. Он работает нормально.

function ptTriplet() {

var a = 0, b = 0 , c = 1000;
for (var i = 0; i < 10000000; i++) {
    a = i;
    c = 1000 - i;
    for (var j = 0; j < c; j++) {

        c--;
        b = 1000 - Math.abs(a) - Math.abs(c);

        if(c < 0)
            break;

        if(a*a+b*b==c*c && a > 0 && b > 0)
            return a +""+ b +""+ c;
    }
}

}

Ответ 15

#include <math.h>

#include <stdio.h>

int main() {

const int sum = 1000;

int a;

for (a = 1; a < 1000; a++) {

    int b;

    for(b = a + 1; b < 1000; b++) {

    int c = sum - a- b;

    {

        if ( (a+b+c == 1000) && (a*a + b*b== c*c) )

           printf("a=%d, b=%d, c=%d\n",a,b,c);

    }

    }

}

return 0;

}

Ответ 16

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

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

Ответ 17

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

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

Ответ 18

вот решение в С++. легко понять.

//Special Pythagorean triplet
#include<stdio.h>

int main()
{
    int a=1,b=2,c=3,sum = 0;

    for(a = 1; a <= 1000;a++)
    {
        for(b = 2; b <= 1000;b++)
        {
            for(c = 3; c <= 1000;c++)
            {
                if(a*a + b*b == c*c && a + b + c == 1000)
                {
                    printf(" %d %d %d",a,b,c);
                    sum = a * b * c;
                    printf("\n");
                    a++;
                    b++;
                    c++;
                }
            }
        }
    }
    printf("Your product is : %d\n",sum);
    return 0;
}

Ответ 19

Как есть два уравнения (a+b+c = 1000 & aˆ2 + bˆ2 = cˆ2) с тремя переменными, мы можем решить его в линейном времени, просто перебирая все возможные значения одной переменной, а затем мы можем решить другие 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;
        }
    }