Trova terna pitagorica per la quale a + b + c = 1000
https://stackoverflow.com/questions/2817848
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Una terna pitagorica è un insieme di tre numeri naturali, un 2 + b 2 = c 2
Per esempio, 3 2 + 4 2 = 9 + 16 = 25 = 5 2 .
esiste esattamente un terna pitagorica per il quale a + b + c = 1000. Trova l'abc del prodotto.
sorgente : http://projecteuler.net/index .php? sezione = problemi & id = 9
ho provato, ma non sapeva dove il mio codice è andato storto. Ecco il mio codice in 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();
}
Soluzione
#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;
}
spiegazione:
- b = a;
se a, b (a <= b) ec sono la tripletta di Pitagora,
poi b, a (b> = a) ec - anche la soluzione, in modo che possiamo cercare solo caso - c = 1000 - a - b; E 'una delle condizioni del problema (non abbiamo bisogno per la scansione di tutti i possibili 'c': basta calcolarla)
Altri suggerimenti
Sono ^ paura non fa quello che pensi lo fa in C. La cosa migliore è quella di utilizzare a*a per piazze interi.
Ecco una soluzione che utilizza la formula di Euclide ( link ).
Facciamo un po 'di matematica: In generale, ogni soluzione avrà la forma
a=k(x²-y²)
b=2kxy
c=k(x²+y²)
dove k, x ed y sono numeri interi positivi, y Ora, a + b + c = kx²-ky² + 2kxy + kx² + ky² = 2kx² + 2kxy = 2kx (x + y) = 1000 divisione per 2: kx (x + y) = 500 Ora abbiamo impostato s = x + y: KXS = 500 Ora siamo alla ricerca di soluzioni di KXS = 500, dove k, x ed s sono interi e Si può ancora migliorare questa: Per n = 1000, il programma deve controllare sei valori per x e seconda delle particolari di realizzazione fino a un valore per y. Questo terminerà prima di rilasciare il pulsante. x < s < 2x.
Poiché tutti dividono 500, possono solo assumono i valori 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Alcuni pseudocodice farlo per n arbitrario (e può essere fatto a mano facilmente per 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
Come menzionato sopra, è ^ xor bit a bit, non potere.
È possibile anche rimuovere il terzo ciclo, e di utilizzare invece
c = 1000-a-b; e ottimizzare questo un po '.
Pseudocodice
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
C'è una soluzione piuttosto sporca ma veloce a questo problema. Date le due equazioni
una * a + b * b = c * c
a + b + c = 1000.
È possibile dedurre la seguente relazione
a = (1000 * 1000-2000 * b) / (2000-2b)
o dopo due semplici trasformazioni di matematica, si ottiene:
a = 1000 * (500-B) / (1000 - b)
dal momento che una deve essere un numero naturale. Da qui è possibile:
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Si è risultato 200 e 375.
In bocca al lupo
#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;
}
Non ho ancora testato questo, ma dovrebbe impostare sulla strada giusta.
Da 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,
, come si vede, pow sta usando l'aritmetica in virgola mobile, che è improbabile per darvi il risultato esatto (anche se in questo caso dovrebbe essere OK, come relativamente piccoli interi hanno una rappresentazione esatta, ma non si basano su quello per genere casi) ... uso n*n quadratura del numeri interi aritmetica (anche, nella moderna CPU è con potenti unità in virgola mobile il throughput può essere anche superiore a virgola mobile, ma la conversione da intero a virgola mobile ha un costo molto elevato numero di cicli di CPU, quindi se hai a che fare con i numeri interi, cercano di attenersi a aritmetica intera).
alcuni pseudocodice per ottimizzare un po 'vostro 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
In C i ^ operatore calcola bit xor, non il potere. Usa x*x invece.
Come altri hanno detto è necessario capire l'operatore ^. Inoltre l'algoritmo produce risposte multiple equivalenti con i parametri a, b e c in ordine diverso.
Mentre come molti hanno fatto notare che il codice funziona bene una volta che si decide di utilizzare gli pow. Se siete interessati ad imparare un po 'di teoria matematica in quanto si applica a CS, mi sento di raccomandare cercando di implementare una versione più effient usando "la formula di Euclide" per la generazione di terne pitagoriche ( link ).
So che questa domanda è abbastanza vecchio, e tutti sono stati soluzioni pubblicazione con 3 cicli for, che non è necessario. Ho ottenuto questo risolto in O (n), da **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
Quindi, risolvendo inoltre otteniamo;
a+b = 1000-c
(a+b)^2 = (1000-c)^2
Se risolviamo ulteriormente si deduce a;
a = ((50000- (1000 * b)) / (1000-b)). Noi ciclo per "b", e trovare "a".
Una volta che abbiamo "a" e "b", otteniamo "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;
}
metodo Euclide dà il perimetro per essere m (m + n) = p / 2 dove m> n ed i lati sono m ^ 2 + n ^ 2 è l'ipotenusa e le gambe sono 2mn e m ^ 2-n ^ 2.thus m (m + n) = 500 dà rapidamente m = 20 e n = 5. I lati sono 200, 375 e 425. Usa Euclide per risolvere tutte le questioni primitive pythorean.
Poiché ci sono due equazioni (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) con tre variabili, possiamo risolverli in tempo lineare semplicemente scorrendo tutti i possibili valori di una variabile, e quindi si può risolvere le altre 2 variabili nel tempo costante.
Dalla prima formula, otteniamo b=1000-a-c, e se sostituiamo b in 2a formula con questo, otteniamo c^2 = aˆ2 + (1000-a-c)ˆ2, che semplifica al c=(aˆ2 + 500000 - 1000a)/(1000-a).
Poi abbiamo un ciclo tra tutti i possibili valori di a, risolvere C e B con le formule di cui sopra, e se vengono soddisfatte le condizioni che abbiamo trovato la nostra tripletta.
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;
}
}
Credo che l'approccio migliore è questa:
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;
}
spiegazione:
Noi riferiremo alla costante N e A in modo da non dover utilizzare due cicli.
Siamo in grado di farlo perché
c=n-a-b e b = (a^2-(a-n)^2)/(2(a-n))
Ho avuto queste formule risolvendo un sistema di equazioni:
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
}
Le risposte di cui sopra sono abbastanza buone, ma manca un pezzo importante di informazioni a + b> c . ;)
sarà fornito Maggiori dettagli a coloro che chiedono.
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)
Ulteriore ottimizzazione dalla risposta di Oleg. Un lato non può essere superiore alla somma degli altri due. Quindi, a + b non può essere inferiore a 500.
