reales - propiedades asociativas
Encontrar triplete de Pitágoras para el cual a+b+c=1000 (16)
Aquí hay una solución usando la fórmula de Euclides ( link ).
Hagamos un poco de matemáticas: en general, cada solución tendrá la forma
a=k(x²-y²)
b=2kxy
c=k(x²+y²)
donde k, x e y son enteros positivos, y <x y gcd (x, y) = 1 (Ignoraremos esta condición, lo que conducirá a soluciones adicionales. Esos pueden descartarse posteriormente)
Ahora, a + b + c = kx²-ky² + 2kxy + kx² + ky² = 2kx² + 2kxy = 2kx (x + y) = 1000
Divide entre 2: kx (x + y) = 500
Ahora configuramos s = x + y: kxs = 500
Ahora estamos buscando soluciones de kxs = 500, donde k, x y s son enteros y x < s < 2x . Dado que todos ellos dividen 500, solo pueden tomar los valores 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Algunos seudocódigo para hacer esto por n arbitraria (puede 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
Aún puedes mejorar esto:
- x nunca será más grande que la raíz de n / 2
- el bucle para s puede comenzar en x y detenerse después de que se haya pasado 2x (si la lista está ordenada)
Para n = 1000, el programa debe verificar seis valores para x y, dependiendo de los detalles de la implementación, hasta un valor para y. Esto terminará antes de que sueltes el botón.
Un triplete de Pitágoras es un conjunto de tres números naturales, a <b <c, para el cual, a 2 + b 2 = c 2
Por ejemplo, 3 2 + 4 2 = 9 + 16 = 25 = 5 2 .
Existe exactamente un triplete de Pitágoras para el que a + b + c = 1000. Encuentre el producto abc.
Fuente : http://projecteuler.net/index.php?section=problems&id=9
Lo intenté pero no sabía dónde salió mal mi código. 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();
}
Como hay dos ecuaciones ( a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2 ) con tres variables, podemos resolverlo en tiempo lineal simplemente repasando todos los valores posibles de una variable, y luego podemos resolver las otras 2 Variables en tiempo constante.
De la primera fórmula, obtenemos b=1000-ac , y si reemplazamos b en la segunda fórmula con esto, obtenemos c^2 = aˆ2 + (1000-ac)ˆ2 , que se simplifica a c=(aˆ2 + 500000 - 1000a)/(1000-a) .
Luego repasamos todos los valores posibles de a, resolvemos c y b con las fórmulas anteriores y, si se cumplen las condiciones, hemos encontrado nuestro triplete.
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();
}
}
}
}
}
}
Como otros han mencionado, es necesario comprender el operador ^ También su algoritmo producirá múltiples respuestas equivalentes con los parámetros a, b y c en diferentes órdenes.
Como se mencionó anteriormente, ^ es xor bitwise, no potencia.
También puede eliminar el tercer bucle y, en su lugar, utilizar c = 1000-ab; Y optimizo 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
Creo que el mejor enfoque aquí es este:
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;
}
}
Explicación: Nos referiremos a la constante N y A, por lo que no tendremos que usar dos bucles. Podemos hacerlo porque c=nab y b = (a^2-(an)^2)/(2(an)) Obtuve estas fórmulas al resolver un sistema de ecuaciones:
a+b+c=n , a^2+b^2=c^2
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 puede ver, pow usa aritmética de punto flotante, lo que probablemente no le dará el resultado exacto (aunque en este caso debería estar bien, ya que los enteros relativamente pequeños tienen una representación exacta, pero no confían en eso para los casos generales). .. use n*n para cuadrar los números en aritmética de enteros (también, en las CPU modernas con unidades de punto flotante potentes, el rendimiento puede ser incluso mayor en punto flotante, pero la conversión de número entero a punto flotante tiene un costo muy alto en número de CPU ciclos, así que si estás tratando con números enteros, trata de mantener la aritmética de números enteros).
Algunos pseudocódigos para ayudarte a optimizar un poco tu 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
El método de 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. Usa Euclides para resolver todas las preguntas primitivas de Pythorean.
En C, el operador ^ calcula el bit a bit xor, no la potencia. Utilice x*x lugar.
Hay una solución bastante sucia pero rápida a este problema. Dadas las dos ecuaciones
a * a + b * b = c * c
a + b + c = 1000.
Puedes deducir la siguiente relación.
a = (1000 * 1000-2000 * b) / (2000-2b)
o después de dos transformaciones matemáticas simples, obtienes:
a = 1000 * (500-b) / (1000 - b)
ya que un 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)
Consiguió el resultado 200 y 375.
Buena suerte
Me temo que ^ no hace lo que crees que hace en C. Tu mejor apuesta es usar a*a para los cuadrados enteros.
Sé que esta pregunta es bastante antigua, y todos han estado publicando soluciones con 3 para bucles, que no es necesario. Conseguí esto resuelto en O (n), al **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2** **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
Entonces, resolviendo más adelante obtenemos;
a+b = 1000-c
(a+b)^2 = (1000-c)^2
Si resolvemos más a fondo lo deducimos a;
a = ((50000- (1000 * b)) / (1000-b)). Hacemos un bucle para "b", y encontramos "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;
}
Si bien muchas personas han señalado que su código funcionará bien una vez que cambie a usar pow . Si está interesado en aprender un poco de teoría matemática, ya que se aplica a CS, recomendaría intentar implementar una versión más eficiente utilizando la "fórmula de Euclides" para generar triples de Pitágoras ( link ).
#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;
}
Las respuestas anteriores son lo suficientemente buenas, pero faltan datos importantes a + b> c . ;)
Más detalles serán proporcionados a aquellos que pregunten.
#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) yc son el triplete de Pitágoras,
luego b, a (b> = a) yc - también la solución, por lo que podemos buscar solo un caso - c = 1000 - a - b; Es una de las condiciones del problema (no necesitamos escanear toda la ''c'' posible: simplemente calcularlo)
#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 debería ponerte en el camino correcto.
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;
}
Optimización adicional de la respuesta de Oleg. Un lado no puede ser mayor que la suma de los otros dos. Así que a + b no puede ser inferior a 500.