Encuentra Pitágoras triplete para los que a + b + c = 1,000
https://stackoverflow.com/questions/2817848
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
A de Pitágoras triplete es un conjunto de tres números naturales, a 2 + b 2 = c 2
Por ejemplo, 3 2 + 4 2 = 9 + 16 = 25 = 5 2 .
No existe exactamente un triplete de Pitágoras para la que a + b + c = 1,000. Encontrar el abc del producto.
Fuente : http://projecteuler.net/index .php? section = problemas & id = 9
He intentado, pero no sabía donde mi código que salió mal. Aquí está mi código en 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();
}
Solución
#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;
}
explicación:
- b = a;
si a, b (a <= b) y c son el triplete de Pitágoras,
a continuación, B, A (b> = a) yc - también la solución, por lo que podemos buscar sólo un caso - c = 1,000 - a - b; Es una de las condiciones del problema (que no necesitamos para escanear todos los posibles 'c': simplemente calcularlo)
Otros consejos
Estoy ^ miedo no hace lo que usted cree en C. Su mejor opción es utilizar a*a para los cuadrados enteros.
Aquí hay una solución según la fórmula de Euclides ( enlace).
Hagamos un poco de matemática: En general, cada solución tendrá la forma
a=k(x²-y²)
b=2kxy
c=k(x²+y²)
donde k, x e y son números enteros positivos, y Ahora, a + b + c = kx²-ky² + 2kxy + kx² + ky² = 2kx² + 2kxy = 2kx (x + y) = 1000 Dividir por 2: kx (x + y) = 500 Ahora que establece s = x + y: kxs = 500 Ahora estamos buscando soluciones de kxs = 500, donde K, X y s son números enteros y Aún puede mejorar esta: Para n = 1000, el programa tiene que comprobar seis valores para x y, dependiendo de los detalles de implementación hasta un valor para y. Esto terminará antes de soltar el botón. x < s < 2x.
Puesto que todos los dividen 500, que sólo puede tomar los valores 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Algunos pseudocódigo para hacer esto para n arbitraria (y pueden ser hecho a mano fácilmente para 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
Como se mencionó anteriormente, ^ es xor bit a bit, no el poder.
También puede quitar el tercer bucle, y en lugar de utilizar
c = 1000-a-b; y optimizar esto un poco.
Pseudocódigo
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
Hay una solución bastante sucia, pero rápida a este problema. Teniendo en cuenta las dos ecuaciones
a * a + b * b = c * c
a + b + c = 1,000.
Se puede deducir la siguiente relación
a = (1000 * 1000-2000 * b) / (2000-2b)
o después de dos transformaciones matemáticas simples, se obtiene:
a = 1,000 * (500-b) / (1000 - b)
ya que una debe ser un número natural. Por lo tanto usted puede:
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Got resultado 200 y 375.
Buena suerte
#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;
}
No he probado esto, pero se debe establecer en el camino correcto.
De 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,
como se ve, pow está utilizando la aritmética de coma flotante, que es poco probable que le dará el resultado exacto (aunque en este caso debe estar bien, como relativamente pequeños números enteros tienen una representación exacta, pero no se basan en que, por general, casos) ... n*n uso de cuadrar los números en aritmética entera (también, en la CPU moderna es con potentes unidades de punto flotante el rendimiento puede ser aún mayor en coma flotante, pero la conversión de número entero a punto flotante tiene un costo muy alto en el número de ciclos de la CPU, así que si usted está tratando con números enteros, tratar de atenerse a la aritmética de enteros).
Un pseudocódigo para ayudarle a optimizar un poco su algoritmo:
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
En C el operador ^ computa XOR bit a bit, no el poder. Uso x*x lugar.
Como ya han dicho que hay que entender el operador ^. También su algoritmo producirá múltiples respuestas equivalentes a los parámetros a, byc en diferentes órdenes.
Mientras que muchas personas han señalado que su código no tendrán ningún problema una vez que se cambia y utiliza pow. Si estás interesado en aprender un poco de la teoría matemática que se aplica a CS, yo recomendaría tratar de implementar una versión más Prasugrel usando "fórmula de Euclides" para generar ternas pitagóricas ( enlace ).
Sé que esta pregunta es bastante antiguo, y todo el mundo ha sido soluciones de publicación de anuncios con 3 bucles, lo que no es necesario. Tengo esta resuelto en O (n), por **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
Por lo tanto, la solución más nos alejamos;
a+b = 1000-c
(a+b)^2 = (1000-c)^2
Si resolvemos más deducimos a;
a = ((50000- (1000 * b)) / (1000-b)). Nos bucle para "b", y encontrar "a".
Una vez que tenemos "a" y "b", obtenemos "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;
}
método Euclides da el perímetro para ser m (m + n) = p / 2 donde m> n y los lados son m ^ 2 + n ^ 2 es la hipotenusa y las patas son 2mn y m ^ 2-n ^ 2.thus m (m + n) = 500 da rápidamente m = 20 y n = 5. Los lados son 200, 375 y 425. El uso de Euclides para resolver todas las cuestiones primitivas pythorean.
Como hay dos ecuaciones (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) con tres variables, se puede resolver en el tiempo lineal con sólo bucle a través de todos los valores posibles de una variable, y entonces podemos resolver los otros 2 variables en tiempo constante.
A partir de la primera fórmula, obtenemos b=1000-a-c, y si sustituimos b en la segunda fórmula con esto, obtenemos c^2 = aˆ2 + (1000-a-c)ˆ2, lo que simplifica a c=(aˆ2 + 500000 - 1000a)/(1000-a).
Luego bucle a través de todos los valores posibles de una, resolver c y b con las fórmulas anteriores, y si se cumplen las condiciones que hemos encontrado nuestro triplete.
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;
}
}
Creo que el mejor enfoque aquí es la siguiente:
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;
}
explicación:
Nos referiremos a la constante N y A, así que no tendremos que utilizar dos bucles.
Podemos hacerlo porque
c=n-a-b y b = (a^2-(a-n)^2)/(2(a-n))
Tengo estas fórmulas resolviendo un sistema de ecuaciones:
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
}
Las respuestas anteriores son lo suficientemente bueno, pero que falta una pieza importante de información a + b> c . ;)
Más detalles serán proporcionados a los que piden.
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)
Además optimización de la respuesta de Oleg. Uno de los lados no puede ser mayor que la suma de los otros dos. Así que a + b no puede ser inferior a 500.
