größter gemeinsamer Teiler (ggT) berechnen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

hier ist es:

Code: Alles auswählen

zahl = 1
while(zahl < 101):
    print zahl
    zahl = zahl + 1
  
unser Lehrer will uns das mit den Schleifen auch nochmal genauer erklären.
Aber wenn ich es nun schon lernen würde und ihm das ggT Programm zeigen könnte, würde dies meiner Note sicher nicht schlecht tun und ich will es ja auch für mich machen.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Nach 4 Stunden Programmierunterricht sollte man nicht zuviel (von sich) erwarten.

Dann schreib doch mal ein Programm, das zu einer Zahl alle ihre Teiler ausgibt. Das kannst du zwar nicht 1:1 für dein ggT-Programm verwenden, ist aber keine schlechte Übung zum Verständnis.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

@nummerix du soltest dich als Lehrer bei der VHS bewerben
tolle Anleitung
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

sea-live hat geschrieben:@nummerix du soltest dich als Lehrer bei der VHS bewerben
tolle Anleitung
Wenn du dich drüber lustig machen musst, bitte.

Aber was bringt es einem Anfänger, der nach eigener Auskunft gerade einmal 4 Stunden Programmierunterricht hinter sich hat und dessen Code man auch deutlich ansieht, dass er noch ganz am Anfang des Programmierens steht, wenn man ihm - so wie du - einen irgendwoher gezauberten Algorithmus präsentiert, den er zum gegenwärtigen Zeitpunkt gar nicht verstehen kann. Sicher, was es bringt ist, dass sein Programm damit praktisch fertig ist.

Wenn er den langen, steinigen Weg geht, algorithmisch aufwändiger und aus mathematischer Sicht ganz sicher nicht das Optimum, aber dabei versteht, warum er was tut und es sich mit dem deckt, wie er es - ohne Programm - auch durchgeführt hätte, dann hat er damit im Endeffekt für sich mehr gewonnen. Und danach kann er immer noch an den euklidischen Algorithmus herangehen und sich hoffentlich erst einmal klar machen, warum und wie der funktioniert.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Du hast mich Falsch verstanden Ich Finde das super Toll wie du das erklärst deshalb!
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

sea-live hat geschrieben:Du hast mich Falsch verstanden Ich Finde das super Toll wie du das erklärst deshalb!
Oh sorry, dann war das in der Tat ein Missverständnis.
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

numerix hat geschrieben:Nach 4 Stunden Programmierunterricht sollte man nicht zuviel (von sich) erwarten.

Dann schreib doch mal ein Programm, das zu einer Zahl alle ihre Teiler ausgibt. Das kannst du zwar nicht 1:1 für dein ggT-Programm verwenden, ist aber keine schlechte Übung zum Verständnis.
Kannst du mir da vielleicht ne kleine Hilfestellung geben?
Ich weis nicht so ganz wie ich das machen kann.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Du gehst von der kleinsten Zahl aus und der größten + 100(oder höher such dir was passendes) und iterierst über die Zahlen zwischen den beiden vorher genannten.

Wenn du dass geschafft hast versuche zu ermittlen ob die Zahlen teilbar sind.

Dafür solltest du wissen was for-Schleifen sind und wie sie funktionieren, sowie xrange und den Modulo Operator kennen oder dir dazu die Doku ansehen.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

DasIch hat geschrieben:Dafür solltest du wissen was for-Schleifen sind und wie sie funktionieren, sowie xrange und den Modulo Operator kennen oder dir dazu die Doku ansehen.
for-Schleife ist nicht nötig, (x)range auch nicht.

Wenn ihr gerade erst die while-Schleife behandelt habt, genügt das für den Anfang. Im Prinzip gehst du vor wie bei deiner Schleife, die bis 100 zählt.

Im Schleifenrumpf musst du dann prüfen, ob bei der Division der Zahl n, deren Teiler du finden willst, durch die Zahlen, die du durchläufst, ein Rest bleibt. Wenn nicht, muss es ein Teiler sein. Wie das mit dem Rest funktioniert, steht in diesem Thread weiter oben.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

@ Ghost
vieleicht hilft dir der Suchen Button oben auch weiter
es gibt nun schon seit ca 5Jahren immmer wieder das gleiche zu Programmierende GGT(ggT)

wenn du hier suchen benutzt und nach ggT suchst bekommst du super tips und das ergebniss der Leute die Vor dir diese aufgaben lösen mussten!
ansonsten wäre eine Konkrete frage zum Programmieren Programmablauf oder syntax von Python wünschenswert!

wie nummerix schon erläuterte hilft dir hier jeder gerne mit einem Problem

nur fertige programme und auch programmierkurse wirst du vergebens suchen!
guckst du hier
http://www.python-forum.de/topic-13472. ... hlight=ggt
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

Hallo,
habe mir da nun mal was zusammen gebastelt. Ich glaube Programmieren kann man das nicht mehr nennen oder?
Aber es funktioniert :D

Code: Alles auswählen

print "Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus."
print
zahl1 = input("Bitte geben Sie die 1. Zahl ein ")
zahl2 = input("Bitte geben Sie die 2. Zahl ein ")
teiler = 0
while(teiler == 0):
 if zahl1 > zahl2:
         teiler = zahl1 / zahl2
         rest = zahl1 % zahl2
         print zahl1, "/", zahl2, "=" ,teiler,"Und der Rest ist:" ,rest
 else:
         teiler = zahl2 / zahl1
         rest = zahl2 % zahl1
         print zahl2, "/", zahl1, "=" ,teiler,"Und der Rest ist:" ,rest


 if rest == 0:
     if zahl1 > zahl2:
         ergebnis = zahl1 / teiler
         print "Der groesste gemeinsame Teiler =",ergebnis
         
         
     else:
         ergebnis = zahl2 / teiler
         print "Der groesste gemeinsame Teiler =",ergebnis
         


 if zahl1 > zahl2:
         teiler = zahl2 / rest
         rest2 = zahl2 % rest
         print zahl2, "/", rest, "=" ,teiler,"Und der Rest ist:" ,rest2
 else:
         teiler = zahl1 / rest
         rest2 = zahl1 % rest
         print zahl1, "/", rest, "=" ,teiler,"Und der Rest ist:" ,rest2

 if rest2 == 0:
    if zahl1 > zahl2:
         print "Der groesste gemeinsame Teiler =",rest
         break
         
    else:
         print "Der groesste gemeinsame Teiler =",rest
         break
 teiler = rest / rest2
 rest3 = rest % rest2
 print rest, "/", rest2, "=" ,teiler,"Und der Rest ist:" ,rest3
 if rest3 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest2
      break

 teiler = rest2 / rest3
 rest4 = rest2 % rest3
 print rest2, "/", rest3, "=" ,teiler,"Und der Rest ist:" ,rest4
 if rest4 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest3
      break
 
 teiler = rest3 / rest4
 rest5 = rest3 % rest4
 print rest3, "/", rest4, "=" ,teiler,"Und der Rest ist:" ,rest5
 if rest5 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest4
      break

 teiler = rest4 / rest5
 rest6 = rest4 % rest5
 print rest4, "/", rest5, "=" ,teiler,"Und der Rest ist:" ,rest6
 if rest6 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest5
      break

 teiler = rest5 / rest6
 rest7 = rest5 % rest6
 print rest5, "/", rest6, "=" ,teiler,"Und der Rest ist:" ,rest7
 if rest7 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest6
      break

 teiler = rest6 / rest7
 rest8 = rest6 % rest7
 print rest6, "/", rest7, "=" ,teiler,"Und der Rest ist:" ,rest8
 if rest8 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest7
      break
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Ghost hat geschrieben:Hallo,
habe mir da nun mal was zusammen gebastelt. Ich glaube Programmieren kann man das nicht mehr nennen oder?
Aber es funktioniert :D
:roll:

Ich teile deine Einschätzung, was das Programmieren angeht ...

Nein, es funktioniert nicht. Es funktioniert nur dann, wenn die Anzahl der erforderlichen Divisionen nicht größer als 8 ist.

Vielleicht wartest du doch besser, bis der Lehrer es nochmal erläutert hat. :wink:
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Code: Alles auswählen

[dasich@tux ~]$ python test.py 
Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus.

Bitte geben Sie die 1. Zahl ein 10
Bitte geben Sie die 2. Zahl ein 20
20 / 10 = 2 Und der Rest ist: 0
Der groesste gemeinsame Teiler = 10
Traceback (most recent call last):
  File "test.py", line 35, in <module>
    teiler = zahl1 / rest
ZeroDivisionError: integer division or modulo by zero
Tatsächlich ist die durchnummerierung von Namen ein sicheres Indiz dafür dass irgendwas schief läuft und verbessert werden kann/sollte. In diesem Fall funktioniert auch dein Algorithmus nicht (immer), was dass primäre Problem ist. Befasse dich erstmal damit und versuche dass dann auf Python zu übertragen.
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

@dasIch,
den Fehler habe ich nun behoben.



Aber vielleicht kannste mir das ja mal ein bisschen umprogrammieren, damit ich mal sehe wie das sein muss.
Vielleicht so das ich das hier:

teiler = rest6 / rest7
rest8 = rest6 % rest7
print rest6, "/", rest7, "=" ,teiler,"Und der Rest ist:" ,rest8
if rest8 == 0:
print "Also ist der groesste gemeinsame Teiler",rest7
break

nicht immer wiederholen muss. Da gibt es doch sicher eine bessere lösung. oder?




Code: Alles auswählen

print "Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus."
print
zahl1 = input("Bitte geben Sie die 1. Zahl ein ")
zahl2 = input("Bitte geben Sie die 2. Zahl ein ")
teiler = 0
while(teiler == 0):
 if zahl1 > zahl2:
         teiler = zahl1 / zahl2
         rest = zahl1 % zahl2
         print zahl1, "/", zahl2, "=" ,teiler,"Und der Rest ist:" ,rest
 else:
         teiler = zahl2 / zahl1
         rest = zahl2 % zahl1
         print zahl2, "/", zahl1, "=" ,teiler,"Und der Rest ist:" ,rest


 if rest == 0:
     if zahl1 > zahl2:
         ergebnis = zahl1 / teiler
         print "Der groesste gemeinsame Teiler =",ergebnis
         break
     else:
         ergebnis = zahl2 / teiler
         print "Der groesste gemeinsame Teiler =",ergebnis
         break
         
 if zahl1 > zahl2:
         teiler = zahl2 / rest
         rest2 = zahl2 % rest
         print zahl2, "/", rest, "=" ,teiler,"Und der Rest ist:" ,rest2
 else:
         teiler = zahl1 / rest
         rest2 = zahl1 % rest
         print zahl1, "/", rest, "=" ,teiler,"Und der Rest ist:" ,rest2

 if rest2 == 0:
    if zahl1 > zahl2:
         print "Der groesste gemeinsame Teiler =",rest
         break
         
    else:
         print "Der groesste gemeinsame Teiler =",rest
         break
 teiler = rest / rest2
 rest3 = rest % rest2
 print rest, "/", rest2, "=" ,teiler,"Und der Rest ist:" ,rest3
 if rest3 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest2
      break

 teiler = rest2 / rest3
 rest4 = rest2 % rest3
 print rest2, "/", rest3, "=" ,teiler,"Und der Rest ist:" ,rest4
 if rest4 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest3
      break
 
 teiler = rest3 / rest4
 rest5 = rest3 % rest4
 print rest3, "/", rest4, "=" ,teiler,"Und der Rest ist:" ,rest5
 if rest5 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest4
      break

 teiler = rest4 / rest5
 rest6 = rest4 % rest5
 print rest4, "/", rest5, "=" ,teiler,"Und der Rest ist:" ,rest6
 if rest6 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest5
      break

 teiler = rest5 / rest6
 rest7 = rest5 % rest6
 print rest5, "/", rest6, "=" ,teiler,"Und der Rest ist:" ,rest7
 if rest7 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest6
      break

 teiler = rest6 / rest7
 rest8 = rest6 % rest7
 print rest6, "/", rest7, "=" ,teiler,"Und der Rest ist:" ,rest8
 if rest8 == 0:
      print "Also ist der groesste gemeinsame Teiler",rest7
      break
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Ghost hat geschrieben:nicht immer wiederholen muss. Da gibt es doch sicher eine bessere lösung. oder?
Teil das ganze bitte sinnvoll in Funktionen ein.

Wenn ich morgen bisschen Zeit hab schau ich ob ich dir ein bisschen was davon machen kann.
Ohloh | Mein Blog | Jabber: segfaulthunter@swissjabber.eu | asynchia – asynchrone Netzwerkbibliothek

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

Das wäre echt klasse. Danke :)
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

@Ghost: Es wurde zwar schon gesagt, aber wenn Du anfängst und Variablen durchzunummerieren und / oder Teilaglgorithmen in fast identischer Art und Weise zig mal hinzuschreiben, dann läuft das quasi immer darauf hinaus, dass da eine Schleife fehlt. Schau Dir doch einmal noch mal genau den Algo auf wikipedia an und schau, wann der Algo terminiert. Diese Bedingung muss in der Schleife irgend wie abgefangen werden. Guck Dir doch mal die Zeile an

Code: Alles auswählen

while teiler == 0:
Was bedeutet das? Solange die Variable teiler den Wert 0 hat, führe den Schleifenrumpf aus. Laut Algo willst Du aber eher so etwas haben: Solange der teiler eben nicht gleich 0 ist, mache etwas! Also muss man da zunächst ansetzen.

Wirf mal alles aus dem Rumpf noch einmal raus! Dann überlege Dir noch einmal genau, wie der Algo abläuft. Was kann in einem Durchlauf der Schleife berechnet werden? Wann fängt ein neuer Durchlauf an. Wie merkt man, dass man die Schleife nicht erneut durchlaufen muss?
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

Nabend Hyperion,

ja ich dachte mir auch schon das die Schleife irgendwie anders aufgebaut sein muss.
Ich werde dann morgen mal weiter probieren. Bin für jede Hilfestellung dankbar.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Boh Ey das man aus 3 Zeilen Queellcode soviel rausgenerieren kann ist selbst mir als Heavy Basic User neu

Code: Alles auswählen

print "Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus."
print
zahl1 = input("Bitte geben Sie die 1. Zahl ein ")
zahl2 = input("Bitte geben Sie die 2. Zahl ein ")


def Euclid (a,b):
    if (b == 0) :
        return a
    else :
        return Euclid (b, (a % b))

print Euclid(zahl1,zahl2)
das tut es doch auch !
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dass es kürzer, schneller, eleganter, besser etc. geht, bestreitet ja niemand und deine Lösung ist auch noch verhältnismäßig lang. Kurz ist z.B.

Code: Alles auswählen

a, b = 35, 14
ggT = lambda a,b: ggT(b,a%b) if b else a
print ggT(a,b)
Aber das hilft Ghost doch nicht, weil er es nicht versteht. Er muss erstmal mit dem Thema "while-Schleife" vernünftig klarkommen.
Antworten