Satz des Pythagoras mit Brute Force
-
akari schrieb:
Hallo
Nur wie überprüfe ich nun, ob das Ergebnis korrekt ist?
Indem du sicherstellst, das du einen richtigen Algorithmus hast
Ich glaube ja das es richtig ist, da die meisten hier aber fähiger sind als ich können Sie es ja vielleiht am code erkennen?
-
Hallo
Dann kann ich dich beruhigen : Dein Code liefert korrekte Ergebnisse.
Und du kannst ja auch Code und Ergebnis mit dem von Sid2K6 vergleichen.Wie "schorsch code" schon sagt, kann man bei gleichen a,b,c noch die Berechnung überspringen.
bis bald
akari
-
Nun ja, was das korrekte Ergebnis betrifft: Das kommt darauf an, ob du ein Dreieck mit der Seitenlänge 0 als Dreieck ansehen willst.
-
Ehm... ich bin verwirrt.
ICh habe nun - wegen dem korrekten Einwand das es keine Dreiecke mit Seitenlänge 0 gibt - die Startwerte von a,b,c auf 1 gesetzt.
Nun gibt es statt 1773 möglichen Pyramdiden plötzlich "nur" noch 772?
Also ist mein Ansatz doch fehlerhaft?
-
Sieht für mich korrekt aus. Bedenke, daß durch die Herrausnahme von 0 sehr viele Kombinationen von a, b und c wegfallen.
-
Man könnte noch berücksichtigen, dass a und b ja vertauschbar sind (b-Schleife bei a beginnen lassen) und das c größer als a und b sein muß (c-Schleife bei b+1 beginnen lassen).
-
Ist die "Optimierung" von braunstein nicht eher noch ein Problem im Code? Es wird ja jedes Dreieck 2x gezaehlt oder nicht? Also z.B wird das Dreieck 3,4,5 einmal gezaehlt fuer a=3, b=4 und c=5, und einmal fuer a=4, b=3 und c=5, oder nicht?
Ich wuerde also a von 1 bis 498, b von a+1 bis 499 und c von b+1 bis 500 laufen lassen.
EDIT: achja, wegen dem "zusaetzlich" in der Aufgabenstellung gehe ich btw davon aus, dass du auch alle richtigen Kombinationen ausgeben sollst. Bin aber nicht 100% sicher.
-
Die Aufgabe haben wir Mal in der Schule bearbeitet...
Und hier wäre ein Ansatz, bei dem man sich die dritte Schleife sparen kann:
for(a = 1; a<500; a++) {
for(b = a+1; b<500; b++) {
c=sqrt(a*a+b*b);
if(int(c) == c) { //Überprüfen: ist c ganzzahlig?
zaehlvariable++;
cout<<a<<""<<a<<"+"<<b<<""<<b<<"="<<c<<endl;
}
}
}
cout<<"Es gibt "<<zaehlvariable<<" rechtwinklige Dreiecke"<<endl;Ach ja: Diese Dreiecke, deren Katheten und Hypotenuse ganzzahlig sind, nennt man
Pythagoräische Zahlentrippel
-
Ehm.. also ich hab die Aufgabe abgenommen bekommen, allerdings mit dem Hinweis, dass man Sie optimieren könne (ich sagte ihm zwar, dass man mir hier mitteilte bruteforce wäre nie wirklich optimal [so ich das nu richtig verstanden habe?], aber das war ihm egal ^^)
Er meinte man sollte zumindest berücksichtigen das a und b nie größer als c sein können.
Nun ist es egal, die Aufgabe ist abgenommen, aber wie ich das realisiere, würde mich dennoch interessieren. Einfach in die for Bedingungen noch ein a bzw b <c hinein?
-
Du kannst die Anfangswerte der Schleifen auch so anpassen, wie du es benötigst:
const int max_len=500; int anzahl=0; for(int a=1;a<max_len;++a) for(int b=a+1;b<max_len;++b) for(int c=b+1;c<max_len;++c) if(a*a+b*b==c*c) anzahl+=2;(Die Schleife findet alle rechtwinkligen Dreiecke mit a<b<c - und da zu jedem derartigen Dreieck ein symmetrisches existiert, zähle ich die gefundenen Dreieecke doppelt)
-
ehm... mal langsam... Könntest Du mir vielleicht die Einzelschritte erklären? ich sehe zwar die Änderungen, sehe aber nicht wirklich den "Knackpunkt" der nun halt sagt "a ist kleiner als c also muss ich nicht arbeiten" (mal ganz für doofe gesprochen)
-
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).
-
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?
-
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.
-
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?
-
Ich glaub', jetzt hat er's.
-
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
-
...
-
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