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

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
User
Beiträge: 482
Registriert: Donnerstag 22. Mai 2008, 09:09

Ghost hat geschrieben:

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
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

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
User
Beiträge: 482
Registriert: Donnerstag 22. Mai 2008, 09:09

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Pekh hat geschrieben: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
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

Pekh hat geschrieben: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
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

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
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

Kann es sein das ich die Schleife zu früh benutze. Und das ich diese erst ab Schritt 4 benutzen muss?
Pekh
User
Beiträge: 482
Registriert: Donnerstag 22. Mai 2008, 09:09

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
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

@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
User
Beiträge: 1
Registriert: Donnerstag 25. September 2008, 17:18

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
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

X2x hat geschrieben:Das Problem ist denke ich mal,
das die Funktion "def" noch nicht benutzt wurde.
Keyword ;) SCNR
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

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
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

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
User
Beiträge: 482
Registriert: Donnerstag 22. Mai 2008, 09:09

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.
Ghost
User
Beiträge: 25
Registriert: Dienstag 23. September 2008, 06:02

So ich habe nun nach etlichen Stunden des Probierens und Kopfzerbrechens ein funktionierendes Programm geschrieben mit dem man den ggT ausrechnen kann.
Für die meisten von euch wäre das sicher ne Sache von 5 Minuten gewesen und sicher ist meins nicht der beste Weg, aber hauptsache er funktioniert nun erstmal :)

Ich danke euch allen für die tolle Hilfe, ohne euch hätte ich das nie hinbekommen.
EINEN SUPER GROßEN DANK AN EUCH.
Hier das funktionierende Programm: :)

Code: Alles auswählen

#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
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
#Anfang der Schleife
rest = 1
while(rest != 0):
    rest = zahl_gross % zahl_klein
    teiler = zahl_gross / zahl_klein
    print zahl_gross,"/",zahl_klein,"=",teiler,"und der Rest ist:", rest
    zahl_gross = zahl_klein
    zahl_klein = rest

#Ausgabe des ggT
if rest == 0:
        print "Der groesste gemeinsame Teiler von",zahl1,"und",zahl2,"ist",zahl_gross
Benutzeravatar
jens
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Spontan fällt mir folgendes ein, um die größere und kleinere Zahl zu bekommen:

Code: Alles auswählen

zahl_gross = max([zahl1, zahl2])
zahl_klein = min([zahl1, zahl2])
Noch einfacher:

Code: Alles auswählen

zahl_klein, zahl_gross = sorted([zahl1, zahl2])
IMHO ist es keine gute Idee, input() zu nehmen! Besser ist es raw_input() mit einem int() oder float(), siehe: [wiki]Thema Sicherheit#Input[/wiki]

GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Super, dass du durchgehalten hast.
Nur ein Denkanstoß noch: Wieso vergleichst du zweimal, welche Zahl die größere ist?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

@Ghost: Und denk mal über Zeile 32 nach. :wink:
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

@Ghost: Wie Du hoffentlich / vermutlich gelernt hast, ist es enorm wichtig zu kapieren, ob und wann man eine Variable manipuliert! In diesem Falle hattest Du das ja eben einmal vergessen und bist deshalb zuvor gescheitert :-)
Aber immerhin hast Du es mit ein wenig Hilfe nun rausgefunden und wirst in Zukunft daher Fehler ähnlicher Art zunächst selber durchdenken und beheben. Erkenntnis ist der Schlüssel zum Erfolg :-)

Als Verbesserungsvorschlag werde ich mal ein, sich mit Funktionen zu befassen und das ganze als solche umzuschreiben. Ansatz:

Code: Alles auswählen

def get_ggt(value1, value2):
    # was auch immer nötig ist ;-)
    return ggt 
So kann man die Funktion bei weiterführenden Probleme nutzen, wie etwa Bruchrechnung o.ä.

Im Zusammenhang mit Funktionen kannst Du dann auch dein Modul so umschreiben, dass kein mehr Code auf Modulebene steht: [wiki]Import[/wiki]
Antworten