Autor Beitrag
Anika
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ausblenden 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=0and (b mod 2=0and (c mod 2=0)) then
  if not((a mod 3=0and (b mod 3=0and (c mod 3=0)) then
  if not((a mod 4=0and (b mod 4=0and (c mod 4=0)) then
  if not((a mod 5=0and (b mod 5=0and (c mod 5=0)) then
  if not((a mod 6=0and (b mod 6=0and (c mod 6=0)) then
  if not((a mod 7=0and (b mod 7=0and (c mod 7=0)) then
  if not((a mod 8=0and (b mod 8=0and (c mod 8=0)) then
  if not((a mod 9=0and (b mod 9=0and (c mod 9=0)) then
  if not((a mod 10=0and (b mod 10=0and (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 user profile iconTh69: Code- durch Delphi-Tags ersetzt
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 868
Erhaltene Danke: 144

Win7
VS 2013, VS2015
BeitragVerfasst: Mo 03.12.12 12:15 
Ja, das Programm sieht in der tat ineffizient aus 8)
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4430
Erhaltene Danke: 906


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Mo 03.12.12 12:25 
Warum sollte eigentlich 33 44 55 keine Lösung sein?
Anika Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8420
Erhaltene Danke: 433

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.2 CE
BeitragVerfasst: 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

ausblenden Delphi-Quelltext
1:
 if (ggT(a,b) = 1and (ggT(a,c) = 1and (ggt(b,c) = 1then					


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

_________________
Oel ngati kameie.

Für diesen Beitrag haben gedankt: Anika
Anika Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 403
Erhaltene Danke: 97

Win 7
D6 Prof, XE2 Prof
BeitragVerfasst: Mo 03.12.12 12:51 
Bitte nicht so kompliziert!
Mein Algo für Zahlen bis MaxZahl:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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
ausblenden Delphi-Quelltext
1:
 if (ggT(a,b) = 1and (ggT(a,c) = 1and (ggt(b,c) = 1then					

besser
ausblenden Delphi-Quelltext
1:
 if (ggt(c,ggT(a,b)) = 1then					

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". :wink:

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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4430
Erhaltene Danke: 906


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Mo 03.12.12 13:20 
Zitat:
sondern immer in der Nähe meiner "geliebten Schüler". :wink:

Geliebte Schüler? Klar :angel:
Die Lesen hier bestimmt mit oder?
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 03.12.12 13:37 
user profile iconRalf Jansen hat folgendes geschrieben Zum zitierten Posting springen:
Die Lesen hier bestimmt mit oder?

"Geliebte Schüler" steht in Anführungszeichen. :wink:
Es ist zwar im Moment Mittagspause und die Computerräume sind voll, aber Lesen, hier! Niemals. :hair:
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mo 03.12.12 16:11 
Sorry für OT, aber:

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1569
Erhaltene Danke: 273


Delphi 10 Seattle Prof.
BeitragVerfasst: Mo 03.12.12 16:44 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden Delphi-Quelltext
1:
 if (ggT(a,b) = 1and (ggT(a,c) = 1and (ggt(b,c) = 1then					

besser
ausblenden Delphi-Quelltext
1:
 if (ggt(c,ggT(a,b)) = 1then					

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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 03.12.12 17:17 
Hallo Aya,
user profile iconAya hat folgendes geschrieben Zum zitierten Posting springen:
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. :roll:
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.

user profile iconNersgatt hat folgendes geschrieben Zum zitierten Posting springen:
Nicht unbedingt. ...

Stimmt. Allerdings hat es mir keine Ruhe gelassen und ich habe mal schnell ein Testprogramm geschrieben:
Variante 1:
ausblenden Delphi-Quelltext
1:
if (ggt(a,b)=1and (ggt(a,c)=1and (ggt(b,c)=1then					

"gegen" Variante 2:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mo 03.12.12 17:35 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1964
Erhaltene Danke: 15

MacOSX 10.6.7
Xcode / C++
BeitragVerfasst: Mo 03.12.12 17:53 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo Aya,
user profile iconAya hat folgendes geschrieben Zum zitierten Posting springen:
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. :roll:
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.

Keine sorge, als Frauenfeindlich hatte ich es nicht im Ansatz interpretiert :)
Ich wollte nur sagen das es nicht unbedingt etwas so außergewöhnliches ist. (und ich mir immer im ersten Moment wenn jemand soetwas zu mir sagt etwas doof vorkomme, so als ob ich was besonderes wäre oder einfach nur total komisch wegen dem was ich mache ^^)

Aber jetzt mal lieber genug mit OT von mir, sorry dafür :oops:

Aya

_________________
Aya
I aim for my endless dreams and I know they will come true!
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2615
Erhaltene Danke: 1419

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 03.12.12 18:07 
Hallo Aya,
user profile iconAya hat folgendes geschrieben Zum zitierten Posting springen:
Aber jetzt mal lieber genug mit OT von mir, sorry dafür :oops:

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,
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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.

user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: Mo 03.12.12 19:04 
Durch die viele Hilfe von euch habe ich mein Programm fertig bekommen.

ausblenden 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<=2500and (c * c = cquadrat) then
  begin
  if (ggt(a,b)=1and (ggt(a,c)=1and (ggt(b,c)=1then
  listbox1.items.add(inttostr(a)+' '+inttostr(b)+' '+inttostr(c));
  end;
  end;
end;

Es ist richtig schnell.
Nochmals vielen Dank an alle.

Anika
WasWeißDennIch
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 653
Erhaltene Danke: 160



BeitragVerfasst: 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):
ausblenden volle Höhe 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:
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<=2500and (sqr(c) = cquadrat) then
        begin
          if (ggt(a,b)=1and (ggt(a,c)=1and (ggt(b,c)=1then
            listbox1.items.add(Format('%d %d %d', [a, b, c]));
        end;
      end;
  finally
    ListBox1.Items.EndUpdate;
  end;
end;
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4049
Erhaltene Danke: 838

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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