Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Triple bis z^2 <= n finden
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Triple bis z^2 <= n finden
 
Autor Nachricht
kulturfenster
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 28.01.2007
Beiträge: 348
Wohnort: Nerdpol

BeitragVerfasst am: 23 Apr 2008 - 13:34:17    Titel: Triple bis z^2 <= n finden

Hallo zusammen,

Ich muss gerade ein Programm schreiben, womit alle Pytagoreischen Tripel (a^2 + b^2 = c^2) ermittelt werden sollen. zB (3,4,5)

Mein Programm soll nun eine Obergrenze n als Parameter erhalten, was alle Tripels bis z^2 <= n ausgibt.

weiss jemand, wie man Tripels findet? Im Netz habi leider nur Lösungsansätze gefunden, die in eine andere Richtung gehen und mir deshalb nicht weiterhelfen konnten,.


Vielen Dank für TIpps!
peristroika
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 18.07.2005
Beiträge: 49

BeitragVerfasst am: 23 Apr 2008 - 14:38:11    Titel:

Da du ja keine Programmiersprache spezifiziert hast, hier die Loesung in Haskell:

pyth n = [(x,y,z) | x<-[1..n/2], y<-[1..n/2], z<-[1..n/2ghc], x^2+y^2==z^2, z^2<n]

Smile Tja... so einfach kanns gehen...
kulturfenster
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 28.01.2007
Beiträge: 348
Wohnort: Nerdpol

BeitragVerfasst am: 23 Apr 2008 - 14:45:11    Titel:

ich war eigentlich eher auf der Suche nach einer mathematischen Lösung, die ich dann implementieren kann. Oder Pseudocode wäre auch super.

oder könntest du deinen Code etwas ausführen?

meine Vermutung:
x, y werden inkrementiert bis n/2.
Was bedeutet n/2ghc?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24256

BeitragVerfasst am: 24 Apr 2008 - 18:55:56    Titel:

Hallo!

Es kommt darauf an, wie naiv du an die Sache heran gehen willst.

Die naivste Methode:

Man lasse x,y und z jeweils von -sqrt(n) bis sqrt(n) laufen, überprüfe für jedes Tripel, ob x^+y^2=z^2 ist, und gebe es im positiven Fall aus.


Etwas mehr Überlegen führt zu folgender Idee:

Man lasse x von 0 bis sqrt(n) laufen, y von 0 bis x, und prüfe für jedes solche Paar nach, ob x^2+y^2 kleiner oder gleich n und vor allem eine Quadratzahl ist (*). Wenn ja, so setze man z:=sqrt(x^2+y^2) und gebe nun alle Tripel (+-x,+-y,+-z) und (+-y,+-x,+-z) aus, wobei die Vorzeichen jeweils unabhängig voneinander in den drei Komponenten gewählt werden können.

Dies kann man auch noch verschärfen, in dem man y nur bis min(x, sqrt(n-x^2)) laufen lässt, dann kann man den Test, ob x^2+y^2<=n ist, sich auch einsparen. (**)

zu (*): Man kann testen, ob eine nicht-negative ganze Zahl Z eine Quadratzahl ist, indem man nur Ganzzahl-Arithmetik verwendet.

Dazu beachte man, dass summe(i=1 bis n) (2i-1) = n^2 ist. Will man also testen, ob Z eine Quadratzahl ist, so zieht man nacheinander aufsteigend die ungeraden natürlichen Zahlen von Z ab, bis das Ergebnis <=0 ist. Im Falle, dass das Ergebnis dann wirklich 0 ist, war Z eine Quadratzahl. Wahr 2n-1 die letzte ungerade Zahl, die man dabei abgezogen hat, so ist n^2=Z. Ist das Ergebnis echt negativ gewesen, so wahr Z keine Quadratzahl.

Bemerkung (**): Bei dem Verfahren ist das n aus der ungeraden Zahl (2n-1), welche als letzte von z abgezogen wurde, bevor der Wert negativ wurde, die größte ganze Zahl mit n^2<=Z.


investiert man noch etwas mehr Theorie, so gelangt man zur folgenden schönen Aussage:

Jedes pythagoräische Tripel lässt sich darstellen als x:=c*(m^2-n^2), y:=c*(2mn) und z:=c*(m^2+n^2), mit ganzen Zahlen m,n, c; oder aber die Def. von x und y ist umgekehrt.

Damit sind also alle pythagoräischen Tripel abgedeckt, d.h. du must nur entspr. Schleifen über c, m und n laufen lassen, und hast alle pythagoräischen Tripel sofort dastehen. Smile


Grüße,
Cyrix
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Triple bis z^2 <= n finden
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum