Satz des Pythagoras mit Brute Force

Hm. Das Quadrat der Hypotenuse entspricht der Summe der Quadrate der Katheten. (wo die hs hingehören...)

Das heisst, du musst eigentlich 500 Hypotenusen betrachten.

Dein Ansatz wäre aber:

int treffer = 0;
    std::cout << "Liste rechtwinkliger Dreiecke, deren Seitenlängen alle ganze Zahlen von 1 bis 500 sind:\n";
    std::cout << "a= Ankathete, b=Gegenkathete, c = Hypotenuse\n";

    for (int hypo = 1; hypo < 500; ++hypo) // hypotenuse;
        for (int anka = 1; anka < 500; ++anka) // ankathete
            for (int geka = 1; geka < 500; ++geka) // gegenkathete
                if (  (hypo * hypo) == (geka * geka) + (anka * anka) )
                {                    
                    std::cout << "Dreieck " << ++treffer 
                    << "  a=" << anka 
                    << ", b=" << geka 
                    << ", c=" << hypo << "\n";

                }

    std::cout << treffer << " rechtwinklige Dreiecke gefunden, deren Seitenlängen ganze Zahlen sind.";
    system("pause");

Die Sonderfallbehandlung müsstest du allerdings selbst nachtragen...

ThaRealMatix

ich ... naja glaube ich habs...

#include <iostream>
using namespace std;

int main()
{
	int a;
	int b;
	int c;	
	int total=0;

	for (a=0; a<=500; a++)
	{
		for (b=0; b<=500; b++)
			for (c=0; c<=500; c++)
		if(a*a+b*b==c*c)
		{
			total++;
		}
	}

		cout << "Es gibt genau: " << total <<" Pyramiden";

	return 0;
}

Nur wie überprüfe ich nun, ob das Ergebnis korrekt ist?

Und falls es richtig ist: Ist der Code "uneffizient?

Gleichseitige Dreiecke sind nicht rechtwinklig.

akari

Hallo

Nur wie überprüfe ich nun, ob das Ergebnis korrekt ist?

Indem du sicherstellst, das du einen richtigen Algorithmus hast

Ist der Code "uneffizient?

Brute Force ist immer uneffizient. Die Umsetzung des verfahrens mit C++ Mitteln ist aber korrekt und effizient (für einen Anfänger)

bis bald
akari

ThaRealMatix

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?

akari

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

Z2

Nun ja, was das korrekte Ergebnis betrifft: Das kommt darauf an, ob du ein Dreieck mit der Seitenlänge 0 als Dreieck ansehen willst.

ThaRealMatix

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?

Z2

Sieht für mich korrekt aus. Bedenke, daß durch die Herrausnahme von 0 sehr viele Kombinationen von a, b und c wegfallen.

Braunstein

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).

Shinja

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.

ne0r

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

ThaRealMatix

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?

CStoll

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)

ThaRealMatix

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)

CStoll

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).

ThaRealMatix

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?

CStoll

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.

ThaRealMatix

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?

CStoll

Ich glaub', jetzt hat er's.