größter gemeinsamer Teiler (ggT) berechnen

[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!

[Ghost]

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.

So müsste es doch eigentlich passen oder?

1.
Zahlen der größte nach Sortieren

2.
Die grössere durch die kleinere Zahl teilen

3.
Die kleinere Zahl durch den Rest teilen

4.
Den grösseren Rest durch den kleineren teilen, solange bis der rest Null ist.

5.
Der letzte Rest ist der ggT

[Hyperion]

Wenn Du Deinen Code mal ablaufen lässt, siehst Du doch schon was faösch läuft! Da stehen immer wieder die selben Zahlen. Denk mal über Schritt 4 nach!

Nimm Dir ein Zahlenbeispiel und lass deinen Code laufen. Dann rechne mal den serten Durchlauf der Schleife auf dem Papier nach. Dann vergleiche mal die Ergebnisse und dann rechne mal den zweiten Schritt auf dem Papier nach und überlege Dir, wieso Du da "weiter" kommst als in Deinem Programm.

Sollte das alleine nicht ausreichen gucke Dir noch mal meine while-Beispiele an und gucke mal, wieso die irgend wann beendet werden bzw. was ich da manipuliere. Dann überlege Dir, was Du manipulierst.

[Ghost]

Kann es sein das ich die Schleife zu früh benutze. Und das ich diese erst ab Schritt 4 benutzen muss?

[Pekh]

Nein, prinzipiell geht es schon so, wie du es jetzt angelegt hast. Nur der Inhalt der Schleife muß ein wenig anders geschrieben werden.

[sea-live]

@Ghost
Ich würde dich als Programmier Neuling noch bitten dir gleich anzugewöhnen in einer PC basierten Progrsammiersprache die nicht Speicheroptimiert sein muss auch ganze Ausdrücke
wie zahl_gross anstatt zahlg zuverwenden das hilft dann ungemein beim durchlesen!
Diesen Hinweeis hat auch bestimmt dein EDV Lehrer gegeben!
wenn nicht stell mal im unterricht diese Frage bezüglich Variablewnnamen und Speicher !

ansonsten tolles vorgehen deinerseits!
wie du siehst gibt hier auch keiner bei einem noch so banalen thema auf dich zuunterstützen!

den nun auch schon mehrmals Geäuserten Wunsch nach Funktionen (def)

solltest du annehmen denn da kommt viel bei rum
in sachen variablen Benenungen und positionierung!

[X2x]

Das Problem ist denke ich mal,
das die Funktion "def" noch nicht benutzt wurde.

Nun stellt sich die Frage ob der Lehrer eine Lösung mit den bisher erlernten mitteln wünscht
oder auf Flexible Schüler die einen Schritt weiter gehen hofft.

[DasIch]

Das Problem ist denke ich mal,
das die Funktion "def" noch nicht benutzt wurde.

Keyword SCNR

[Ghost]

Ich bedanke mich erstmal für alle Hilfestellungen. Ist echt prima das einem hier so geholfen wird.


von der def funktion habe ich gar keine ahnung.
Hatte ich auch noch nie was mit gemacht. habe also keine ahnung wie ich die unterbringen kann oder wie sie funktioniert.

[Ghost]

So hier mal ein neuer Versuch der auch noch nicht ganz in Ordnung ist.
Bei den Zahlen 1029 und 1071 klappt es aber.
Aber bei mehreren rechen Schritten klappt es wieder nicht, also muss wohl was an der Schleife nicht stimmen. Kann mir da bitte jemand helfen?
Denn er wiederholt die Schleife einfach immer wieder anstatt weiter zu rechnen. Und ich habe keine Ahnung warum er das macht.

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 groesse nach sortiert
#1. Zahlen der groesse nach Sortieren
if zahl1 > zahl2:
    zahl_gross = zahl1
else:
    zahl_gross = zahl2
if zahl1 < zahl2:
    zahl_klein = zahl1
else:
    zahl_klein = zahl2
print
print "Die groessere Zahl ist",zahl_gross, "und die kleinere ist",zahl_klein
print

#Verarbeitung
#2. Die groessere durch die kleinere Zahl teilen
teiler = zahl_gross / zahl_klein
rest = zahl_gross % zahl_klein
print zahl_gross,"/",zahl_klein,"=",teiler,"und der Rest ist:", rest

#3. Die kleinere Zahl durch den Rest teilen
teiler2 = zahl_klein / rest
rest2   = zahl_klein % rest
print zahl_klein,"/",rest,"=",teiler2,"und der Rest ist:", rest2

#Schleife
#4. Den groesseren Rest durch den kleineren teilen, solange bis der rest Null ist
rest3 = 1
while(rest3 != 0):
    teiler3 = rest / rest2
    rest3 = rest % rest2
    print rest,"/",rest2,"=",teiler3,"und der Rest ist:", rest3

#Ausgabe des Ergebnisses
#5. Der letzte Rest ist der ggT
if rest3 == 0:
    print "Der groesste gemeinsame teiler von",zahl_gross,"und",zahl_klein,"ist",rest2

[Pekh]

Es liegt daran, daß 'rest2' sich nie ändert. Außerdem solltest du die beiden ersten Schritte ebenfalls in der Schleife unterbringen. Um dein Schema von oben mal zu modifizieren:

1) Zahlen der Größe nach Sortieren

2) Schleife betreten

3) Größere Zahl durch die kleinere Zahl teilen, Rest merken. Sicherstellen, daß die größere Zahl im nächsten Durchlauf die jetzige kleinere Zahl, und die kleinere Zahl im nächsten Durchlauf der jetzige Rest ist.

4) Wenn der Rest 0 beträgt, Schleife abbrechen.