Autor |
Beitrag |
Anika
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Mo 03.12.12 11:50
Guten Tag.
Ich bin jetzt in Informatik und soll alle Pythagoras-Zahlen bis 2500 berechnen. Mein Lehrer ist irgendwo und ich weiß nicht weiter.
Mein Programm ist
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure TForm1.BerechnenClick(Sender: TObject); var a,b,c:integer; begin for a:=1 to 2500 do for b:=a to 2500 do for c:=b to 2500 do if a*a+b*b=c*c then if not((a mod 2=0) and (b mod 2=0) and (c mod 2=0)) then if not((a mod 3=0) and (b mod 3=0) and (c mod 3=0)) then if not((a mod 4=0) and (b mod 4=0) and (c mod 4=0)) then if not((a mod 5=0) and (b mod 5=0) and (c mod 5=0)) then if not((a mod 6=0) and (b mod 6=0) and (c mod 6=0)) then if not((a mod 7=0) and (b mod 7=0) and (c mod 7=0)) then if not((a mod 8=0) and (b mod 8=0) and (c mod 8=0)) then if not((a mod 9=0) and (b mod 9=0) and (c mod 9=0)) then if not((a mod 10=0) and (b mod 10=0) and (c mod 10=0)) then listbox1.items.add(inttostr(a)+' '+inttostr(b)+' '+inttostr(c)); end; |
Wenn ich das Programm starte dauert es sehr lange bis ich Ergebnisse bekomme.
Und dann sind auch noch Zahlen drin, die nicht rein sollen, zum Beispiel 33 44 55. Ich kann doch aber nicht alle Zahlen überprüfen. Ich habe schon probiert mit einer for-to-Schleife alle Zahlen als Teiler rauszuwerfen, aber dann dauert das Programm noch länger.
Vielleicht kann mir einer von euch helfen. Vielen Dank.
Anika
Moderiert von Th69: Code- durch Delphi-Tags ersetzt
|
|
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Mo 03.12.12 12:15
Ja, das Programm sieht in der tat ineffizient aus
Ich habe für dich mal gescuht, und diese Seite gefunden: www.arndt-bruenner.d...ts/pythagotripel.htm
Da steht sogar eine Formel, wie du alle möglichen Tripel erzeugen kannst - das sollte dann wesentlich schneller gehen
Für diesen Beitrag haben gedankt: Anika
|
|
Anika
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Mo 03.12.12 12:18
Danke, Danke, Danke für deine Antwort.
Es sieht ziemlich kompliziert aus. Aber ich werde es schon verstehen.
Gerade haben wir die Aufgabe als Hausuafgabe bekommen, da keiner etwas hingekriegt hat.
Anika
|
|
Ralf Jansen
Beiträge: 4705
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Mo 03.12.12 12:25
Warum sollte eigentlich 33 44 55 keine Lösung sein?
|
|
Anika
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Mo 03.12.12 12:28
Wir sollen nur Zahlen finden, die keinen Teiler gemeinsam haben. Warum weiß ich nicht. Vielleicht sind es sonst zu viele.
33 44 55 sind doch durch 11 teilbar und darum sollen sie nicht angezeigt werden.
Anika
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 03.12.12 12:37
Ah, ok. Dann würde ich da einen Größter-Gemeinsamer-Teiler-Test einbauen. D.h. die ganzen Mod-Bedingen ersetzen durch
Delphi-Quelltext 1:
| if (ggT(a,b) = 1) and (ggT(a,c) = 1) and (ggt(b,c) = 1) then |
Zur Berechnung des ggT: Wikipedia, Euklidischer Algorithmus.
Edit: Die 3.Schleife mit dem c kannst du dir sparen: Teste, ob a^2 + b^2 eine Quadratzahl ist, d.h. if (sqrt(a*a + b*b) * (sqrt(a*a + b*b) = (a*a + b*b) then ...
_________________ We are, we were and will not be.
Für diesen Beitrag haben gedankt: Anika
|
|
Anika
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Mo 03.12.12 12:42
Vielen Dank. Das ist eine gute Idee.
Wenn ich heute nachmittag zu hause bin, werde ich es gleich probieren.
Vielen Dank für die Hilfe.
Jetzt habe ich noch Englisch und Chemie.
Tschüss Anika
|
|
mandras
Beiträge: 430
Erhaltene Danke: 107
Win 10
Delphi 6 Prof, Delphi 10.4 Prof
|
Verfasst: Mo 03.12.12 12:51
Bitte nicht so kompliziert!
Mein Algo für Zahlen bis MaxZahl:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| 1. Erstelle Feld (Matrix), evtl. Shortint um Speicher zu sparen, der Dimension [1.. MaxZahl, 1..MaxZahl] und belege alle Werte mit "-1" (=Status des Zahlenpaars ist unbekannt) 2. für i=1 .. Maxzahl und j=i+1 .. Maxzahl: Wenn Feld[i,j]=-1 (also unbekannter Status des Paares (i,j) dann: Wenn sqrt (i*i+j*j) ganze Zahl dann: Feld [i,j] := 1 // Zahlenpaar (i,j) ist korrekte Lösung und weiterhin(wichtig!): Alle Feld [i*x,j*x] mit i*x<=Maxzahl und j*x<Maxzahl auf 0 setzen. Bedeutet: Diese Zahlenpaare sind nur Vielfache der gefundenen Lösung, also für die weitere Berechnung überspringen
3. Ausgabe der Ergebnisse (gebe alle (i,j,i*i+j*j) aus, für die gilt: Feld[i,j]=1) |
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 03.12.12 13:14
Hallo,
Gausis Hinweis mit der Berechnung des ggT wird genau das sein, was Du benötigst.
Eine kleine Ergänzung. Da Dein Programm ja schneller werden soll, würde ich statt
Delphi-Quelltext 1:
| if (ggT(a,b) = 1) and (ggT(a,c) = 1) and (ggt(b,c) = 1) then |
besser
Delphi-Quelltext 1:
| if (ggt(c,ggT(a,b)) = 1) then |
verwenden. Es spart zumindest eine ggT-Berechnung und sollte ggT(a,b)=1 sein, wird der 2.Euklidische Algorithmus sehr schnell durchlaufen.
Ansonsten finde ich es lustig, dass scheinbar überall ähnliche Aufgaben gestellt werden. Nur ich bin dann nicht "irgendwo", sondern immer in der Nähe meiner "geliebten Schüler".
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Für diesen Beitrag haben gedankt: Anika
|
|
Ralf Jansen
Beiträge: 4705
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Mo 03.12.12 13:20
Zitat: | sondern immer in der Nähe meiner "geliebten Schüler". |
Geliebte Schüler? Klar
Die Lesen hier bestimmt mit oder?
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 03.12.12 13:37
Ralf Jansen hat folgendes geschrieben : | Die Lesen hier bestimmt mit oder? |
"Geliebte Schüler" steht in Anführungszeichen.
Es ist zwar im Moment Mittagspause und die Computerräume sind voll, aber Lesen, hier! Niemals.
Dafür gibt es viel zu viel "wunderschöne", geistlose Möglichkeiten im Netz.
Und sollten sie es lesen, ist es auch egal. Die kennen mich!
Ich bin ohnehin verwundert, dass es ein Mädchen (ich nehme an, es ist ihr richtiger Name) hier in die EE geschafft hat und vor allem auch etwas lernen will.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Aya
Beiträge: 1964
Erhaltene Danke: 15
MacOSX 10.6.7
Xcode / C++
|
Verfasst: Mo 03.12.12 16:11
Sorry für OT, aber:
Mathematiker hat folgendes geschrieben : | Ich bin ohnehin verwundert, dass es ein Mädchen (ich nehme an, es ist ihr richtiger Name) hier in die EE geschafft hat und vor allem auch etwas lernen will. |
Warum, sooo selten ist das garnicht.
In der Firma wo ich hier bin bestand Zeitweise (ca. 1.5 Jahre) die gesamte Entwicklungsabteilung (3 Leute..) aus Frauen
_________________ Aya
I aim for my endless dreams and I know they will come true!
|
|
Nersgatt
Beiträge: 1581
Erhaltene Danke: 279
Delphi 10 Seattle Prof.
|
Verfasst: Mo 03.12.12 16:44
Mathematiker hat folgendes geschrieben : | Hallo,
Gausis Hinweis mit der Berechnung des ggT wird genau das sein, was Du benötigst.
Eine kleine Ergänzung. Da Dein Programm ja schneller werden soll, würde ich statt
Delphi-Quelltext 1:
| if (ggT(a,b) = 1) and (ggT(a,c) = 1) and (ggt(b,c) = 1) then |
besser
Delphi-Quelltext 1:
| if (ggt(c,ggT(a,b)) = 1) then |
verwenden. Es spart zumindest eine ggT-Berechnung und sollte ggT(a,b)=1 sein, wird der 2.Euklidische Algorithmus sehr schnell durchlaufen.
|
Nicht unbedingt. Beim ersten Konstrukt wird ggT(a,b) = 1 berechnet. Ergibt das Konstrukt FALSE, dann werden in der Regel die beiden anderen ggT nicht mehr berechnet, denn der Gesamtausdruck kann ja gar nicht mehr TRUE werden. Im Idealfall wird also ggT nur einmal aufgerufen. Dieses Verhalten kann man aber über den Compilerschalter {$B+} ändern. (Deshalb "in der Regel")
Bei Deinem Konstrukt muss ggT immer 2x aufgerufen werden.
_________________ Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)
Für diesen Beitrag haben gedankt: Anika
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 03.12.12 17:17
Hallo Aya,
Aya hat folgendes geschrieben : | Warum, sooo selten ist das garnicht.
In der Firma wo ich hier bin bestand Zeitweise (ca. 1.5 Jahre) die gesamte Entwicklungsabteilung (3 Leute..) aus Frauen |
Das war von mir auch nicht frauenfeindlich gemeint. Im Gegenteil.
Nur leider erlebe ich in den letzten Jahren immer mehr, dass sich Schülerinnen praktisch nicht mehr für irgendwelche Naturwissenschaften inkl. Mathematik und Informatik interessieren. Deshalb finde ich es ja sehr schön, wenn es Mädchen und Frauen in dieser Branche gibt.
Nersgatt hat folgendes geschrieben : | Nicht unbedingt. ... |
Stimmt. Allerdings hat es mir keine Ruhe gelassen und ich habe mal schnell ein Testprogramm geschrieben:
Variante 1:
Delphi-Quelltext 1:
| if (ggt(a,b)=1) and (ggt(a,c)=1) and (ggt(b,c)=1) then |
"gegen" Variante 2:
Delphi-Quelltext 1:
| if ggt(ggt(a,b),c)=1 then |
Und das Ergebnis ist vielleicht überraschend. Beide sind gleich(!) schnell.
Der Grund dürfte darin liegen, dass 60,79... % aller zufällig gewählten Paare natürlicher Zahlen teilerfremd sind.
Deshalb führt Variante 1 mit 60 % den 2.Test durch und mit 36 % sogar den dritten, Variante 2 dagegen immer genau 2. Das gleicht sich aus.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mo 03.12.12 17:35
Mathematiker hat folgendes geschrieben : |
Und das Ergebnis ist vielleicht überraschend. Beide sind gleich(!) schnell.
Der Grund dürfte darin liegen, dass 60,79... % aller zufällig gewählten Paare natürlicher Zahlen teilerfremd sind.
Deshalb führt Variante 1 mit 60 % den 2.Test durch und mit 36 % sogar den dritten, Variante 2 dagegen immer genau 2. Das gleicht sich aus.
|
Die 60,79 = 6/Sqr(Pi) gelten nur wenn a,b zufallig gewählt sind, was hier nicht der Fall ist wg. b >= a. Viel wichtiger für die Performance ist allerdings, daß man die b-Schleife abbricht, wenn a^2 + b^2 > 2500^2.
|
|
Aya
Beiträge: 1964
Erhaltene Danke: 15
MacOSX 10.6.7
Xcode / C++
|
Verfasst: Mo 03.12.12 17:53
_________________ Aya
I aim for my endless dreams and I know they will come true!
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 03.12.12 18:07
Hallo Aya,
Aya hat folgendes geschrieben : | Aber jetzt mal lieber genug mit OT von mir, sorry dafür |
Du brauchst Dich nicht zu entschuldigen, Du hast Recht. Ich hoffe, dass es in Zukunft wieder mehr Frauen im Computerbereich gibt. Dies würde dem Computer-"Männerklub" nur gut tun.
Hallo Gammatester,
Gammatester hat folgendes geschrieben : | Die 60,79 = 6/Sqr(Pi) gelten nur wenn a,b zufallig gewählt sind, was hier nicht der Fall ist wg. b >= a. |
Für den Zahlenbereich, denn Anika untersuchen will, ergibt sich für a von 1 bis 2500 und b von a bis 2500 ein Anteil von 60,77% teilerfremde Paare. Danach habe ich die Grenze auf 10000 erhöht. Dann sind es 60,7888%.
Du hast aber Recht, dass die 6/Pi² theoretisch nur für beliebige Zufallspaare gilt.
Gammatester hat folgendes geschrieben : | Viel wichtiger für die Performance ist allerdings, daß man die b-Schleife abbricht, wenn a^2 + b^2 > 2500^2. |
Auf jeden Fall. Ich bestimmt ja gespannt, ob Anika noch ihre Lösung veröffentlicht.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Mo 03.12.12 19:06, insgesamt 1-mal bearbeitet
|
|
Anika
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Mo 03.12.12 19:04
Durch die viele Hilfe von euch habe ich mein Programm fertig bekommen.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
| procedure TForm1.BerechnenClick(Sender: TObject); var a,b,c,cquadrat:integer; function ggt(zahl1,zahl2:integer):integer; var rest:integer; begin repeat rest:=zahl1 mod zahl2; zahl1:=zahl2; zahl2:=rest; until rest=0; ggt:=zahl1; end; begin for a:=1 to 2500 do for b:=a to 2500 do begin cquadrat:=a*a + b*b; c:=trunc(sqrt(cquadrat)); if (c<=2500) and (c * c = cquadrat) then begin if (ggt(a,b)=1) and (ggt(a,c)=1) and (ggt(b,c)=1) then listbox1.items.add(inttostr(a)+' '+inttostr(b)+' '+inttostr(c)); end; end; end; |
Es ist richtig schnell.
Nochmals vielen Dank an alle.
Anika
|
|
WasWeißDennIch
Beiträge: 653
Erhaltene Danke: 160
|
Verfasst: Di 04.12.12 12:09
Es geht auch noch schneller, indem man die Listbox nicht jeden Eintrag einzeln zeichnen lässt. Ich habe mir einmal ein paar kleine Änderungen erlaubt (und eine Einrückung eingeführt, damit man das auch lesen kann):
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35:
| procedure TForm1.BerechnenClick(Sender: TObject); var a,b,c,cquadrat:integer; function ggt(zahl1,zahl2:integer):integer; var rest:integer; begin repeat rest:=zahl1 mod zahl2; zahl1:=zahl2; zahl2:=rest; until rest=0; Result:=zahl1; end; begin ListBox1.Items.BeginUpdate; try ListBox1.Items.Clear; for a:=1 to 2500 do for b:=a to 2500 do begin cquadrat:=sqr(a) + sqr(b); c:=trunc(sqrt(cquadrat)); if (c<=2500) and (sqr(c) = cquadrat) then begin if (ggt(a,b)=1) and (ggt(a,c)=1) and (ggt(b,c)=1) then listbox1.items.add(Format('%d %d %d', [a, b, c])); end; end; finally ListBox1.Items.EndUpdate; end; end; |
|
|
Th69
Beiträge: 4782
Erhaltene Danke: 1055
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Di 04.12.12 12:35
Es geht sogar noch effizienter, wenn man bei c > 2500 aus der (inneren) Schleife springt.
Für diesen Beitrag haben gedankt: Anika
|
|
|