Trouver un triplet Pythagoréen pour lequel a + b + c = 1000

j'ai peur ^ ne pas faire ce que vous pensez qu'il n'en C. Votre meilleur pari est d'utiliser a*a pour les carrés entiers.

Voici une solution utilisant la formule D'Euclide (lien).

faisons quelques calculs: En général, chaque solution aura la forme

a=k(x²-y²)
b=2kxy
c=k(x²+y²)

où k, x et y sont des entiers positifs,y < x et gcd(x, y)=1 (nous ignorerons cette condition, ce qui conduira à des solutions supplémentaires. Ceux-ci peuvent être rejetés par la suite)

maintenant, A+b+c= kx2-ky2+2kxy+kx2+ky2=2kx2+2kxy = 2kx (x+y) = 1000

diviser par 2: kx (x+y) = 500

maintenant nous set s=x+y: kxs = 500

maintenant nous recherchons des solutions de kxs=500, où k, x et s sont des entiers et x < s < 2x. Puisque tous diviser 500, ils ne peuvent prendre que les valeurs 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Un pseudo pour faire cela pour n arbitraire (it et peut être fait à la 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

Vous pouvez encore améliorer cela:

• x ne sera jamais plus grand que la racine de n/2
• la boucle pour s peut commencer à x et arrêter après 2x a été transmise (si la liste est ordonnée)

pour n = 1000, le programme doit vérifier six valeurs pour x et selon les détails de l'implémentation jusqu'à une valeur pour Y. Cela se terminera avant que vous relâchiez le bouton.

Vous pouvez également supprimer la troisième boucle, et au lieu d'utiliser c = 1000-a-b; et optimiser un peu.

Pseudo

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 assez sale mais rapide à ce problème. Compte tenu des deux équations

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 les deux simples de mathématiques de transformation, vous obtenez:

a = 1000*(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) 

résultat Obtenu 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;
}

n'ai pas testé, mais ça devrait vous mettre sur la bonne voie.

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 à virgule flottante, ce qui est peu probable pour vous donner le résultat exact (bien que dans ce cas devrait être OK, car relativement petits entiers ont une représentation exacte; mais ne comptez pas sur cela pour les cas généraux)... utilisez n*n pour quadriller les nombres en arithmétique entière (aussi, dans les CPU modernes avec des unités flottantes puissantes le débit peut être encore plus élevé en virgule flottante, mais la conversion d'entier à floating point a un coût très élevé dans le nombre de cycles CPU, donc si vous avez affaire à des entiers, essayez de coller à l'arithmétique entière).

un pseudo 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

Comme d'autres l'ont mentionné, vous devez comprendre l'opérateur^. Aussi votre algorithme produira des réponses équivalentes multiples avec les Paramètres a, b et c dans des ordres différents.

alors que comme beaucoup de gens ont souligné que votre code fonctionnera bien une fois que vous passez à l'utilisation pow. Si vous êtes intéressé par l'apprentissage d'un peu de théorie mathématique telle qu'elle s'applique à CS, je vous recommande d'essayer d'implémenter une version plus effient en utilisant "la formule D'Euclid" pour générer des triples Pythagoréens (lien).

je sais que cette question est assez ancienne, et tout le monde a posté des solutions avec 3 pour les boucles, ce qui n'est pas nécessaire. J'ai eu ce résolu en O(n), par **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

Donc, la résolution, plus nous avancerons;

a+b = 1000-c

(a+b)^2 = (1000-c)^2

Si nous résolvons les autres nous en déduisons;

a=(50000-(1000*b))/(1000-B)). On boucle pour "b", et de trouver "une".

une Fois que nous avons "a" et "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;
}

en C# il fonctionne très bien) Cependant, sûr que ce n'est pas la meilleure façon de calc))

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();
                    }

                }
           }
       }



    }
}

}

Euclide méthode 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.ainsi 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 primitives de pythore.

Voici mon code en javascript. Il fonctionne très bien.

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;
    }
}

}

#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;

}

je pense que la meilleure approche est ici:

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 nous référerons au N et à une constante pour 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)) J'ai eu 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 une pièce importante de l'information a + b > c. ;)

Plus de détails seront fournis à ceux qui le demandent.

voici la solution en c++. facile à comprendre.

//Special Pythagorean triplet
#include<stdio.h>

int main()
{
    int a=1,b=2,c=3,sum = 0;

    for(a = 1; a <= 1000;a++)
    {
        for(b = 2; b <= 1000;b++)
        {
            for(c = 3; c <= 1000;c++)
            {
                if(a*a + b*b == c*c && a + b + c == 1000)
                {
                    printf(" %d %d %d",a,b,c);
                    sum = a * b * c;
                    printf("\n");
                    a++;
                    b++;
                    c++;
                }
            }
        }
    }
    printf("Your product is : %d\n",sum);
    return 0;
}

Puisqu'il y a deux équations (a+b+c = 1000&&aˆ2 + bˆ2 = cˆ2) avec trois variables, nous pouvons le résoudre en temps linéaire en bouclant toutes les valeurs possibles d'une variable, puis nous pouvons résoudre les 2 autres variables en temps constant.

de la première formule, nous obtenons b=1000-a-c, et si l'on remplace b en 2ème formule avec de ce, nous obtenons c^2 = aˆ2 + (1000-a-c)ˆ2, ce qui simplifie c=(aˆ2 + 500000 - 1000a)/(1000-a).

alors nous bouclons toutes les valeurs possibles de a, résolvons 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;
        }
    }