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

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

27 голосов
/ 12 мая 2010

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

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

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

Ответы [ 16 ]

30 голосов
/ 12 мая 2010

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

29 голосов
/ 12 мая 2010 
#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 - трифлет Пифагора, <br> тогда b, a (b> = a) и c - тоже решение, поэтому мы можем искать только один случай
  • с = 1000-а-б; Это одно из условий проблемы (нам не нужно сканировать все возможные символы 'c': просто рассчитайте)
17 голосов
/ 14 мая 2010

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

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

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

14 голосов
/ 12 мая 2010

Как упомянуто выше, ^ - это бит по 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
12 голосов
/ 09 августа 2010

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

a * a + b * b = c * c

a + b + c = 1000.

Вы можете вывести следующее соотношение

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

или после двух простых математических преобразований вы получите:

а = 1000 * (500-б) / (1000-б)

, поскольку a должно быть натуральным числом. Следовательно, вы можете: 

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

Получил результат 200 и 375.

Удачи

6 голосов
/ 12 мая 2010

С 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
6 голосов
/ 12 мая 2010 
#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;
}

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

5 голосов
/ 12 мая 2010

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

2 голосов
/ 18 июля 2013

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

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

Страница:
...