Trouver triplets pythagoriciens pour lequel a + b + c = 1000
https://stackoverflow.com/questions/2817848
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Un triplet de Pythagore est un ensemble de trois nombres naturels, a 2 + b 2 = c 2
Par exemple, 3 2 + 4 2 = 9 + 16 = 25 = 5 2 .
Il existe exactement un triplet pythagoricien pour lequel a + b + c = 1000. Trouvez l'abc du produit.
Source : http://projecteuler.net/index .php? section = problèmes & id = 9
J'ai essayé, mais ne savait pas où mon code a mal tourné. Voici mon code 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();
}
La solution
#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;
}
explication:
- b = a;
si a, b (a <= b) et c sont le triplet de Pythagore,
puis b, a (b> = a) et c - aussi la solution, afin que nous puissions rechercher un seul cas - c = 1 000 - a - b; Il est l'une des conditions du problème (on n'a pas besoin de scanner possible « c »: calculer juste)
Autres conseils
Je suis ^ peur ne fait pas ce que vous pensez qu'il fait en C. Votre meilleur pari est d'utiliser a*a pour les carrés entiers.
Voici une solution en utilisant la formule d'Euclide ( lien ).
Faisons un peu de mathématiques: En général, chaque solution aura la forme
a=k(x²-y²)
b=2kxy
c=k(x²+y²)
k, x et y sont des nombres entiers positifs, y Maintenant, a + b + c = kx²-ky² + 2kxy + kx² + ky² = 2kx² + 2kxy = 2kx (x + y) = 1000 division par 2: kx (x + y) = 500 Maintenant nous avons mis s = x + y: KXS = 500 Maintenant, nous recherchons des solutions de KXS = 500, où k, x et s sont des entiers et Vous pouvez améliorer encore ceci: Pour n = 1000, le programme doit vérifier six valeurs pour x et selon les détails de la mise en œuvre jusqu'à une valeur pour y. Cela mettra fin à avant de relâcher le bouton. x < s < 2x.
Étant donné que toutes les diviser 500, ils ne peuvent prendre les valeurs 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Certains pseudocode pour ce faire pour n quelconque (et peuvent être fait main facilement pour 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
Comme mentionné ci-dessus, ^ est xor bit par bit, et non pas le pouvoir.
Vous pouvez également supprimer la troisième boucle, et au lieu d'utiliser
c = 1000-a-b; et d'optimiser un peu.
pseudocode
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
Il y a une solution très sale mais rapide à ce problème. Compte tenu des deux équations
a * a * b + b = c * c
a + b + c = 1000.
Vous pouvez déduire la relation suivante
A = (1000 * 1000-2000 * b) / (2000-2b)
ou après deux transformations mathématiques simples, vous obtenez:
a = 1 000 * (500-b) / (1000 - b)
depuis un doit être un nombre naturel. Par conséquent, vous pouvez:
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Got résultat 200 et 375.
Bonne chance
#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;
}
ai pas testé, mais il devrait vous mettre sur la bonne voie.
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,
comme vous le voyez, pow utilise l'arithmétique en virgule flottante, ce qui est peu susceptible de vous donner le résultat exact (bien que dans ce cas devrait être OK, comme des entiers relativement faibles ont une représentation exacte, mais ne comptez pas sur que pour le général cas) ... utilisation n*n de la place des nombres dans l'arithmétique entière (également, dans CPU moderne est avec des unités puissantes à virgule flottante le débit peut être encore plus élevé en virgule flottante, mais la conversion de nombre entier en virgule flottante a un coût très élevé en nombre de cycles CPU, donc si vous avez affaire à des entiers, essayez de tenir à l'arithmétique entière).
certains pseudocode pour vous aider à optimiser un peu votre algorithme:
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 l'opérateur ^ calcule XOR, pas le pouvoir. Utilisez x*x à la place.
Comme d'autres l'ont mentionné, vous devez comprendre l'opérateur ^. De plus, votre algorithme produira plusieurs réponses équivalentes avec les paramètres a, b et c dans des ordres différents.
Alors que beaucoup de gens ont signalé que votre code fonctionnera bien une fois que vous passez à l'aide pow. Si vous êtes intéressé à apprendre un peu de la théorie mathématique qu'il applique à CS, je recommande d'essayer de mettre en œuvre une version plus EFFIENT en utilisant « la formule d'Euclide » pour générer des triplets pythagoriciens ( lien ).
Je sais que cette question est assez vieux, et tout le monde a été des solutions de publication avec 3 pour les boucles, qui ne sont pas nécessaires. Je me suis résolu ce en O (n), par **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
Alors, la résolution de plus nous nous;
a+b = 1000-c
(a+b)^2 = (1000-c)^2
Si nous résolvons plus nous en déduisons à;
a = ((50000- (1000 * b)) / (1000-b)). Nous boucle pour « b » et trouver « un ».
Une fois que nous avons "a" et "b", on obtient "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éthode Euclide donne le périmètre à m (m + n) = p / 2, où m> n et les côtés sont m ^ 2 + n ^ 2 est l'hypoténuse et les jambes sont 2mn et m ^ 2-n ^ 2.thus m (m + n) = 500 donne rapidement m = 20 et n = 5. Les côtés sont 200, 375 et 425. Utilisez Euclide pour résoudre toutes les questions pythorean primitives.
Comme il y a deux équations (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) avec trois variables, nous pouvons le résoudre dans le temps linéaire en boucle seulement à travers toutes les valeurs possibles d'une variable, et nous pouvons résoudre les autres 2 variables dans le temps constant.
De la première formule, nous obtenons b=1000-a-c, et si nous remplaçons b dans la formule 2 avec cela, nous obtenons c^2 = aˆ2 + (1000-a-c)ˆ2, ce qui simplifie à c=(aˆ2 + 500000 - 1000a)/(1000-a).
Ensuite, nous boucle à travers toutes les valeurs possibles d'une, résoudre c et b avec les formules ci-dessus, et si les conditions sont remplies, nous avons trouvé notre triplet.
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;
}
}
Je pense que la meilleure approche ici est la suivante:
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;
}
explication:
Nous appellerons à la constante N et A donc nous ne pas avoir à utiliser deux boucles.
Nous pouvons le faire parce que
c=n-a-b et b = (a^2-(a-n)^2)/(2(a-n))
Je suis arrivé à ces formules en résolvant un système d'équations:
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
}
Les réponses ci-dessus sont assez bon mais il manque un élément d'information important a + b> c . ;)
Plus de détails seront fournis à ceux qui demandent.
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)
Une optimisation de la réponse de Oleg. Un côté ne peut pas être supérieure à la somme des deux autres. Donc, a + b ne peut pas être inférieur à 500.
