größter gemeinsamer Teiler (ggT) berechnen

[Ghost]

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

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

[numerix]

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

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.

[DasIch]

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]

@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

[name]

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.

[Ghost]

Das wäre echt klasse. Danke

[Hyperion]

@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]

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]

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 !

[numerix]

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.

[Ghost]

richtig so ist es.

Ich hätte zwar nun sicher eine perfekte lösung. Dir mir aber gar nichts bringt. Weil ich so gut wie nichts davon verstehe.

Wenn mir jemand zeigen würde wie ich das mit ner while schleife machen kann, würde mir das 1000 mal mehr helfen.

[Hyperion]

Vielleicht solltest Du mal ein wenig mit ner while-Schleife spielen:

Code: Alles auswählen

>>> x = 0
>>> while(x<5):
...     print "x ist nun %d" % x
...     x += 1
...
x ist nun 0
x ist nun 1
x ist nun 2
x ist nun 3
x ist nun 4

Was passiert hier genau? Naja, wir initialisieren x mit dem Wert 0. Dann startet die Schleife. Es wird im Schleifenkopf immer geprüft, ob x < 5 ist. es kommt ein Wahrheitswert heraus, also True oder False. Das kann man einfach nachprüfen (Achtung, direkt nach Ablauf des obigen Codes in derselben Shell, daher ist die erste Auswertung auch False)

Code: Alles auswählen

>>> x<5
False
>>> x=0
>>> x<5
True

Solange bei while ein True herauskommt, wird der Schliefenrumpf immer wieder durchlaufen. Wird bei einer Auswertung False festgestellt, so bricht die Schleife ab und es geht hinter der kompletten Schleife weiter.

Zunächst ist x ja 0 und damit erhalten wir ein True. Also springt unser Programm in die Schleife und gibt brav aus,d ass x gleich 0 ist. Danach erhöhen wir den Wert von x um eins. Damit ist der Schleifenrumpf durchlaufen und das Programm springt wieder in den Kopf und prüft erneut die Bedingung. Oh Wunder, sie wird wieder True und das der Rumpf wird also wieder durchlaufen.

Betrachten wir nun den Fall, dass x im Schleifenkopf 4 ist, also der letzte Durchlauf. x < 5 ist True, also ab in den Rumpf. Dort brav alles ausgeben. Dann wird x aber auf 5 erhöht. Beim nun folgenden Vergleich im Schleifenkopf ist die Aussage x < 5 False! Also springt unser Python Interpreter nicht noch einmal in den Rumpf, sondern direkt hinter den Schleifenrumpf und dort ginge es im Programm weiter (Naja bei uns nicht, da da nichts mehr kommt ^^)

So funktionieren while-Schleifen.

Natürlich ist das Hochzählen nicht die einzige Möglichkeit (im Gegenteil verwendet man bei bekanneter Anzahl an Durchläufen eher eine for-Schleife). Man kann auch folgendes machen:

Code: Alles auswählen

while True:
    print "Noch laeuft der Rechner!"

Auch hier enthält der Schleifenkopf einen Wahrheitswert - wie dieser zustande kommt, ist Python egal! In diesem falle ist er eben statisch und somit wird die Schleife so lange durchlaufen, bis wir das Programm abbrechen.

Schauen wir und doch mal etwas anders an:

Code: Alles auswählen

>>> z = 111
>>> while z:
...     print "z ist grad %d" % z
...     z = z / 2
...
z ist grad 111
z ist grad 55
z ist grad 27
z ist grad 13
z ist grad 6
z ist grad 3
z ist grad 1

Hier zählen wir nicht, sondern manipulieren den Wert von z innerhalb der Schleife durch Division. So etwas ähnliches passiert auch bei Deinem Problem! while bricht also ab, wenn z = 0 ist - kann man leicht nachprüfen:

Code: Alles auswählen

>>> z
0

Oder auch:

Code: Alles auswählen

>>> if z:
...     print "z ist wohl wahr"
...

So, ich denke das war reichlich ausführlich Versuch Dich doch noch mal an Deinem Problem. Auch bei dir wird doch eine Variable bei jedem Durchlauf manipuliert. Du musst Dir nur überlegen, bei welchem Wert der Abbruch erfolgen soll und versuchen diese Bedingung zu modellieren. Das kannst Du einfach in einer Shell nachprüfen, indem Du einfach mal die Bedingung testest, wenn Du Dir dabei nicht sicher bist.

[Pekh]

Gut, nachdem Hyperion mir mit einer ausführlichen Erklärung zuvorgekommen ist, bleibt mir vorerst nur dieses:

Dein Wille zum Verstehen und deine Hartnäckigkeit sind wirklich bewundernswert. Genau diese Eigenschaften habe ich bei meinen Mitschülern und Mitstudenten immer vermißt. Sobald sie eine auch nur annähernde Lösung auf dem Papier oder im Rechner hatten, fiel bei ihnen eine Klappe und sie waren an weiteren Erklärungen nicht weiter interessiert. Und standen dann bei der nächsten Aufgabe mit genau den selben Problemen wieder auf dem Schlauch. Probieren und Herumspielen sind zwei ganz wichtige Zutaten zum Verstehen. Und Python bietet mit dem interaktiven Interpreter einen hervorragenden Sandkasten. Er ist meine erste Anlaufstelle, wenn ich mich mit neuen Befehlen oder Modulen vertraut machen will, oder wenn während der Arbeit an einem Programm Fragen zum Verhalten eines bestimmten Befehls aufkommen.
Wie Hyperion schon schrieb: Lass dein eigentliches Problem erst einmal am Rande liegen und mache dich mit dem Verhalten der While-Schleife in Durchschnitts- und Extremsituationen (Werte rund um die Abbruchbedingung) vertraut. Dann analysiere deinen Algorithmus auf Tätigkeiten, die sich immer auf die gleiche Weise wiederholen. Diese Abfolge von Befehlen stellt die Basis für deinen Schleifenrumpf dar. Dann mußt du dir eine sinnvolle Abbruchbedingung überlegen und die im Rumpf verwendeten Variablen entsprechend anpassen. Für den Anfang ist es sicherlich nicht verkehrt, dir in jedem Schleifendurchlauf den Inhalt aller beteiligten Variablen ausgeben zu lassen. Damit erkennst du dann schneller, was falsch läuft.

Bleib auf diesem Weg - Leuten, die wirklich an den Zusammenhängen interessiert sind, hilft man gerne weiter.

[Ghost]

Danke für die Tolle erklärung
Da kann ich viel mit anfangen. dennoch habe ich zwei Fragen im Moment

was bedeutet hier:

z = 111
while z:
print "z ist grad %d" % z
z = z / 2

das %d??

und while z:
eigentlich dürfte die Schleife doch nie aufhören wenn da nur z steht oder nicht?!
irgendwie verstehe ich das nicht, wenn da nur z oder so steht.

[Leonidas]

das %d??

"Setze den Wert von z als Ganzzahl ein".

Und ``z`` ist so lange war wie lange es Ungleich null ist. Wenn es gleich null ist, wird die Bedingung ``False`` und die Schleife bricht ab.

[Ghost]

Hi Leonidas,
danke für die Hilfe.

Ich habe hier mal was versucht zu "programmieren".

Es funktioniert aber nicht so ganz.
Ist denn der ansatz so richtig, wenn ja, ab wann ist es falsch?

Code: Alles auswählen

# -*- coding: cp1252 -*-
#Programmueberschrift
print "Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus."
print

#Daten
zahl1 = input("Bitte geben Sie die 1. Zahl ein ")
zahl2 = input("Bitte geben Sie die 2. Zahl ein ")

#Zahlen werden der grösse nach sortiert
if zahl1 > zahl2:
    zahlg = zahl1
else:
    zahlg = zahl2
if zahl1 < zahl2:
    zahlk = zahl1
else:
    zahlk = zahl2
print
print "Die groessere Zahl ist",zahlg, "und die kleinere ist",zahlk
print

#Schleife
rest = 1
while(rest):
    teiler = zahlg / zahlk
    rest = zahlg % zahlk
    teiler = zahlk / rest
    teiler = rest / teiler
    print teiler, rest
    

[Pekh]

Code: Alles auswählen

    teiler = zahlg / zahlk
    rest = zahlg % zahlk
    teiler = zahlk / rest
    teiler = rest / teiler
    print teiler, rest
    

Das sieht etwas komisch aus. Ist teiler nun zahlg / zahlk, zahlk / rest oder rest / teiler? Die jeweils anderen beiden Fälle solltest du entfernen oder zumindest in einer anderen Variable ablegen.

[Ghost]

also so?

Code: Alles auswählen

# -*- coding: cp1252 -*-
#Programmueberschrift
print "Dieses Programm rechnet Ihnen den groessten gemeinsamen Teiler zweier Zahlen aus."
print

#Daten
zahl1 = input("Bitte geben Sie die 1. Zahl ein ")
zahl2 = input("Bitte geben Sie die 2. Zahl ein ")

#Zahlen werden der grösse nach sortiert
if zahl1 > zahl2:
    zahlg = zahl1
else:
    zahlg = zahl2
if zahl1 < zahl2:
    zahlk = zahl1
else:
    zahlk = zahl2
print
print "Die groessere Zahl ist",zahlg, "und die kleinere ist",zahlk
print

#Schleife
rest = 1
while(rest):
    teiler = zahlg / zahlk
    rest = zahlg % zahlk
    print teiler, rest

[Pekh]

Jetzt überlege dir mal, woran es liegt, daß sich Teiler und Rest nicht verändern, die Schleife also nur terminiert, wenn der GGT schon beim ersten Durchlauf gefunden wird.

Hinweis: Schreibe dir mal ganz genau auf, wie du auf dem Papier vorgehen würdest: Welche Zahl teilst du im ersten Schritt durch welche, welche im zweiten Schritt und so weiter.

[numerix]

Dein Wille zum Verstehen und deine Hartnäckigkeit sind wirklich bewundernswert. Genau diese Eigenschaften habe ich bei meinen Mitschülern und Mitstudenten immer vermißt. Sobald sie eine auch nur annähernde Lösung auf dem Papier oder im Rechner hatten, fiel bei ihnen eine Klappe und sie waren an weiteren Erklärungen nicht weiter interessiert. Und standen dann bei der nächsten Aufgabe mit genau den selben Problemen wieder auf dem Schlauch.

Bleib auf diesem Weg - Leuten, die wirklich an den Zusammenhängen interessiert sind, hilft man gerne weiter.

Jawoll!