Найдите тройку Пифагора, для которой a + b + c = 1000.
-
26-09-2019 - |
Вопрос
Пифагорейский тройня2 + б2 = с2
Например, 32 + 42 = 9 + 16 = 25 = 52.
Существует ровно одна тройка Пифагора, для которой 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();
}
Решение
#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;
}
объяснение:
- б = а;
если a, b (a <= b) и c — тройка Пифагора,
тогда b, a (b >= a) и c — тоже решение, поэтому мы можем искать только один случай - в = 1000 – а – б;Это одно из условий задачи (нам не нужно сканировать все возможные 'c':просто посчитай)
Другие советы
Я боюсь ^
не делает то, что вы думаете, что это делает в C. Ваша лучшая ставка - использовать a*a
для целочисленных квадратов.
Вот решение с использованием формулы Евклида (связь).
Давайте сделаем немного математики: в целом каждое решение будет иметь форму
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. Это прекратит, прежде чем выпустить кнопку.
Как упомянуто выше, ^ побитовой хор, а не мощность.
Вы также можете удалить третий петлю и вместо этого использовать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 * A + B * B = C * C
A + B + C = 1000.
Вы можете вывести следующие отношения
A = (1000 * 1000-2000 * б) / (2000-2б)
Или после двух простых математических преобразований вы получаете:
A = 1000 * (500-B) / (1000 - б)
Поскольку A должен быть естественным числом. Следовательно, вы можете:
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Получил результат 200 и 375.
Удачи
#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;
}
Не проверил это, но он должен установить вас на правильном пути.
От 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
В C оператор ^ вычисляется побитовые хор, а не мощность. Использовать x*x
вместо.
Как упомянули другие, вам нужно понять оператор ^. Также ваш алгоритм будет производить несколько эквивалентных ответов с параметрами A, B и C в разных заказах.
Пока как у многих людей указали, что ваш код будет работать нормально, как только вы переключитесь на использование pow
. Отказ Если вы заинтересованы в изучении теории математики, поскольку она применяется к CS, я бы порекомендовал попытаться реализовать более эффективную версию с использованием «Формула Евклида» для генерации пифагорейских тройков (связь).
Я знаю, что этот вопрос довольно старый, и все были размещены решения с 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 * б)) / (1000-б)). Мы зацикливаем для «б» и найду «А».
Как только у нас есть «А» и «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;
}
МЕТОД EUCLID дает периметр 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. Используйте евклид для решения всех питоровских примитивных вопросов.
Как есть два уравнения (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;
}
}
Я думаю, что лучший подход вот это:
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 и константу, поэтому нам не придется использовать две петли. Мы можем сделать это, потому чтоc=n-a-b
и б =(a^2-(a-n)^2)/(2(a-n))
Я получил эти формулы, решив систему уравнений:
a+b+c=n
,
a^2+b^2=c^2
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. ;)
Подробнее будут предоставлены тем, кто спрашивает.
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.