3. Satz des Pythagoras mit Brute Force

Satz des Pythagoras mit Brute Force

  • T

    CStoll schrieb:

    Der Knackpunkt sind die Anfangswerte der for-Schleifen. Du kannst "a ist kleiner als b" umkehren zu "b ist größer als a" - und das bedeutet im Endeffekt, daß du b nicht von 1 bis 500 durchrechnen mußt sondern nur von a+1 bis 500 (genauso mit b und c).

    In der Schleife zähle ich also eigentlich nur die Dreiecke, bei denen a die kürzere Kathede ist (die übrigen Dreiecke werden dadurch erfasst, daß ich jeweils +=2 rechne).

    Verstehe ich das richtig, dass durch deinen obigen Code b also quasi nicht bei 1 anfängte sondern bei zwei und dann durch die erhöhung a immer einen voraus ist? Ich muss aber doch dafür sorgen, dass a und b bzw a²+b²<c² ist?

    0
  • C

    Ja, gut erkannt - a startet bei 1 und erhöht sich in jedem Durchlauf der äußersten Schleife um 1. b startet jeweils bei a+1 (im ersten Durchlauf also bei 2, im nächsten bei 3 etc) und erhöht sich in jedem Durchlauf der mittleren Schleife um 1, genauso startet c jeweils bei b+1.

    Und im Rumpf der innersten Schleife sichert die if()-Abfrage, daß die Pythagoras-Bedingung erfüllt ist.

    PS: theoretisch kann man die innereste Schleife auch abbrechen, wenn man ein Pythagoras-Tripel gefunden hat - das wäre eine weitere Optimierung. Oder man nutzt die Dreiecksungleichung aus und läßt c nur bis a+b laufen.

    0
  • T

    Also die if Bedingung überprüft ob der Satz erfüllt ist und zählt die anzahl um zwei hoch, weil es sowhl für a+b wie b+a gilt?

    0
  • C

    Ich glaub', jetzt hat er's.

    0
  • E

    Ist das jetzt bezüglich der zu prüfenden Dreiecke das Minimum? Man müsste bezüglich maximalem a und b in den Schleifen doch noch tiefer gehen können.

    #include <iostream>
#include <cmath>

int main()
{
    const int MAX = 500;
    int proben  = 0;
    int treffer = 0;
    int a_max = 0;
    int b_max = 0;

    std::cout << "Rechtwinklige Dreiecke, deren Seitenlaengen alle ganze Zahlen von 1 bis " << MAX << " sind:\n";
    std::cout << "a=Ankathete, b=Gegenkathete, c=Hypotenuse\n";

    for (int a = 1; a <= MAX-1; ++a) // Ankathete
    {
        for (int b = a + 1; b <= MAX-2; ++b) // Gegenkathete
        {
               ++proben;
               double c = sqrt ( a*a + b*b );
               if ( (int(c) == c) && (c <= MAX) ) 
               {                    
                    std::cout << "Dreieck " << ++treffer
                    << "  a=" << a
                    << ", b=" << b
                    << ", c=" << c << "\n";

                    if ( a > a_max ) a_max = a;
                    if ( b > b_max ) b_max = b;
               }
         }
    }     
    std::cout << proben  << " rechtwinklige Dreiecke geprueft.\n";
    std::cout << 2*treffer << " rechtwinklige Dreiecke gefunden, deren Seitenlaengen ganze Zahlen sind.\n";
    std::cout << "a_max = " << a_max << " b_max = " << b_max << std::endl;
    system("pause");
}

    output:

    123753 rechtwinklige Dreiecke geprueft.
    772 rechtwinklige Dreiecke gefunden, deren Seitenlaengen ganze Zahlen sind.
    a_max = 340 b_max = 483

    0
  • E

    ...

    0
  • E

    Kann man z.B. etwas damit anfangen, dass bei a und b immer eine grundlegende Zahl gerade und die andere ungerade ist? Das kann die Schleife bei b vereinfachen. Die multiplen Tripel ermitteln wir über den ggT, denn interessant sind nur "teilerfremde" Tripel, bei denen a, b den größten gemeinsamen Teiler 1 besitzen.

    Siehe auch: http://www.faust.fr.bw.schule.de/mhb/pythag.htm

    Die Zahl der geprüften Dreiecke kann man etwa auf die Hälfte senken, wenn man b in Doppelschritten erhöht:

    #include <iostream>
#include <cmath>

int ggT(int a,int b)
{
   if(b>a)
      return ggT(b,a);
   if(b!=0)
      return ggT(b,a%b);
   else
       return a;
};

int main()
{
    const int MAX = 500;
    int proben  = 0;
    int treffer = 0;
    int a_max = 0;
    int b_max = 0;

    std::cout << "Teilerfremde \"Pythagoraeische Tripel\" von 1 bis " << MAX << "\n";
    std::cout << "a= Ankathete, b=Gegenkathete, c = Hypotenuse\n";

    for (long long a = 1; a <= MAX-1; ++a) // Ankathete
    {
        for (long long b = a + 1; b <= MAX-2; b+=2) // Gegenkathete
        {
               ++proben;
               double c = sqrt ( a*a + b*b );
               if ( (int(c) == c) && (c <= MAX) && (ggT(b,a)==1) ) 
               {                    
                    std::cout << "Dreieck " << ++treffer
                    << "\ta=" << a
                    << ",\tb=" << b
                    << ",\tc=" << c << "\n";

                    if ( a > a_max ) a_max = a;
                    if ( b > b_max ) b_max = b;
               }
         }
    }     
    std::cout << proben  << " rechtwinklige Dreiecke geprueft.\n";
    std::cout << treffer << " teilerfremde \"Pythagoraeische Tripel\" gefunden\n";
    std::cout << "a_max = " << a_max << " b_max = " << b_max << std::endl;
    system("pause");
}

    output:

    Teilerfremde "Pythagoraeische Tripel" von 1 bis 500
    a= Ankathete, b=Gegenkathete, c = Hypotenuse
    Dreieck 1 a=3, b=4, c=5
    Dreieck 2 a=5, b=12, c=13
    Dreieck 3 a=7, b=24, c=25
    Dreieck 4 a=8, b=15, c=17
    Dreieck 5 a=9, b=40, c=41
    Dreieck 6 a=11, b=60, c=61
    Dreieck 7 a=12, b=35, c=37
    Dreieck 8 a=13, b=84, c=85
    Dreieck 9 a=15, b=112, c=113
    Dreieck 10 a=16, b=63, c=65
    Dreieck 11 a=17, b=144, c=145
    Dreieck 12 a=19, b=180, c=181
    Dreieck 13 a=20, b=21, c=29
    Dreieck 14 a=20, b=99, c=101
    Dreieck 15 a=21, b=220, c=221
    Dreieck 16 a=23, b=264, c=265
    Dreieck 17 a=24, b=143, c=145
    Dreieck 18 a=25, b=312, c=313
    Dreieck 19 a=27, b=364, c=365
    Dreieck 20 a=28, b=45, c=53
    Dreieck 21 a=28, b=195, c=197
    Dreieck 22 a=29, b=420, c=421
    Dreieck 23 a=31, b=480, c=481
    Dreieck 24 a=32, b=255, c=257
    Dreieck 25 a=33, b=56, c=65
    Dreieck 26 a=36, b=77, c=85
    Dreieck 27 a=36, b=323, c=325
    Dreieck 28 a=39, b=80, c=89
    Dreieck 29 a=40, b=399, c=401
    Dreieck 30 a=44, b=117, c=125
    Dreieck 31 a=44, b=483, c=485
    Dreieck 32 a=48, b=55, c=73
    Dreieck 33 a=51, b=140, c=149
    Dreieck 34 a=52, b=165, c=173
    Dreieck 35 a=57, b=176, c=185
    Dreieck 36 a=60, b=91, c=109
    Dreieck 37 a=60, b=221, c=229
    Dreieck 38 a=65, b=72, c=97
    Dreieck 39 a=68, b=285, c=293
    Dreieck 40 a=69, b=260, c=269
    Dreieck 41 a=75, b=308, c=317
    Dreieck 42 a=76, b=357, c=365
    Dreieck 43 a=84, b=187, c=205
    Dreieck 44 a=84, b=437, c=445
    Dreieck 45 a=85, b=132, c=157
    Dreieck 46 a=87, b=416, c=425
    Dreieck 47 a=88, b=105, c=137
    Dreieck 48 a=93, b=476, c=485
    Dreieck 49 a=95, b=168, c=193
    Dreieck 50 a=96, b=247, c=265
    Dreieck 51 a=104, b=153, c=185
    Dreieck 52 a=105, b=208, c=233
    Dreieck 53 a=115, b=252, c=277
    Dreieck 54 a=119, b=120, c=169
    Dreieck 55 a=120, b=209, c=241
    Dreieck 56 a=120, b=391, c=409
    Dreieck 57 a=132, b=475, c=493
    Dreieck 58 a=133, b=156, c=205
    Dreieck 59 a=135, b=352, c=377
    Dreieck 60 a=136, b=273, c=305
    Dreieck 61 a=140, b=171, c=221
    Dreieck 62 a=145, b=408, c=433
    Dreieck 63 a=152, b=345, c=377
    Dreieck 64 a=155, b=468, c=493
    Dreieck 65 a=160, b=231, c=281
    Dreieck 66 a=161, b=240, c=289
    Dreieck 67 a=168, b=425, c=457
    Dreieck 68 a=175, b=288, c=337
    Dreieck 69 a=180, b=299, c=349
    Dreieck 70 a=189, b=340, c=389
    Dreieck 71 a=203, b=396, c=445
    Dreieck 72 a=204, b=253, c=325
    Dreieck 73 a=207, b=224, c=305
    Dreieck 74 a=225, b=272, c=353
    Dreieck 75 a=228, b=325, c=397
    Dreieck 76 a=252, b=275, c=373
    Dreieck 77 a=261, b=380, c=461
    Dreieck 78 a=280, b=351, c=449
    Dreieck 79 a=297, b=304, c=425
    Dreieck 80 a=319, b=360, c=481
    62001 rechtwinklige Dreiecke geprueft.
    80 teilerfremde "Pythagoraeische Tripel" gefunden
    a_max = 319 b_max = 483

    0
Anmelden zum Antworten