größter gemeinsamer Teiler (ggT) berechnen

[Ghost]

Hallo,
ich soll für die Schule ein Programm mit Python schreiben das zwei Zahlen einliest und von den beiden Zahlen den ggT ausgiebt.
Kann mir da jemand bei helfen?
Ich habe nämlich keine Ahnung wie ich da ran gehen soll. Wie man ihn berechnen kann weis ich, aber nicht wie ich das als Programm schreiben soll.
Ich muss dazu sagen das ich noch Anfänger in Sachen Python bin.
Das hier habe ich schonmal, aber keine Ahnung wie ich es weiter machen soll:

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 ")

[EyDu]

Hallo.

Du musst uns schon relevanten Code zeigen oder sagen wo du konkrete Probleme hast. Eine fertige Lösung wird dir sicherlich niemand geben. Siehe auch hier.

[name]

Eine einfache Loesung waere eine schleife und der Modulo operator.

[numerix]

ich soll für die Schule ein Programm mit Python schreiben das zwei Zahlen einliest und von den beiden Zahlen den ggT ausgiebt.
Ich habe nämlich keine Ahnung wie ich da ran gehen soll. Wie man ihn berechnen kann weis ich, aber nicht wie ich das als Programm schreiben soll.

WIE würdest den ggT von zwei Zahlen denn "per Hand" berechnen?
Notiere das doch mal - an einem Zahlenbeispiel - auf dem Papier und sieh dir Schritt für Schritt an, wie du es gemacht hast.

[Ghost]

@ EyDu,

ich möchte ja gar nicht das ihr meine Hausaufgaben macht. Ich möchte nur das ihr mir dabei helft

@ name,

ja was mit ner Schleife habe ich mir auch schon gedacht. Aber da ich nicht weis was der Modulo operator ist werde ich da nun mal nach googeln Danke

@ numerix,

wenn ich jetzt z.B. die Zahlen 70 und 15 hätte würde ich es so machen:

70 ist teilbar durch 1, 2, 5, 7, 10, 14, 35, 70
15 ist teilbar durch 1, 3, 5, 15

Also ist der ggT 5.
Aber wie ich das nun in eine Schleife einbringen kann, das ist mein Problem^^

[numerix]

wenn ich jetzt z.B. die Zahlen 70 und 15 hätte würde ich es so machen:

70 ist teilbar durch 1, 2, 5, 7, 10, 14, 35, 70
15 ist teilbar durch 1, 3, 5, 15

Also ist der ggT 5.

Okay, das wird dann zwar kein besonders effizienter Algorithmus (da gibt es Bessere), macht aber nichts.

Ein erster Schritt auf diesem Weg wäre eine Liste, die alle Teiler einer Zahl enthält. Dazu könntest du z.B. eine Funktion teiler_von(n) definieren, die eine solche Liste zurückliefert.

Um zu prüfen, ob eine Zahl durch eine andere teilbar ist, kannst du den Modulo-Operator % verwenden, der den Rest einer ganzzahligen Division liefert. Gibt es keinen Rest, dann geht die Divison auf und man hat einen Teiler gefunden.

Also könntest du - das ist ebenfalls nicht effizient, aber für den Anfang das einfachste - für alle Zahlen bis zur Zahl n, deren Teiler du bestimmen willst, prüfen, ob sich n durch diese Zahl ohne Rest teilen lässt. Wenn ja: Ab in die Teilerliste.

[EyDu]

Schau dir auf Wikipedia mal den Eintrag zum GGT an. Der dort beschriebene Algorithmus ist total einfach zu implementieren. Das sind vielleicht drei bis vier Zeilen.

Modolu ist Division mit Rest, ein Artikel dazu ist ebenfalls bei der Erläuterung des Algorithmus verlinkt.

[numerix]

Schau dir auf Wikipedia mal den Eintrag zum GGT an. Der dort beschriebene Algorithmus ist total einfach zu implementieren. Das sind vielleicht drei bis vier Zeilen.

Sicher geht es mit dem Euklidischen Algorithmus fix. Aber aus Erfahrung kann ich sagen, dass es nicht jedem leicht fällt, diesen Algorithmus auch zu verstehen. Da wäre dann abzuwägen, ob man sich dafür entscheidet, einen umständlicheren, ineffizieten Algorithmus zu implementieren, den man durch und durch versteht, als einen einfach zu implementierenden, effizienten, von dem man dann zwar feststellt, dass er funktioniert, man aber eigentlicht nicht weiß, wie und warum.

Ich tendiere eher zum ersten Weg und deshalb auch meine Frage vorab, WIE Ghost es per Hand machen würde.

[sea-live]

wiki spukt das aus

also überprüfen welche zahl die grösste
die grössere duch die kleinere
den rest als neuen divisor
der kleineren
den rest als neuer divisor des alten divisors bis rest NULL
somit ist divisor der kleinete GGT
GGT (1071,1029) =21

[Hyperion]

Also auf die Idee bei wikipedia zu schauen könnte man schon kommen - zumal Schüler ansonsten ja auch "clever" alles an Hilfe in Anspruch nehmen, was geht. Und liest man dann ein wenig genauer, könnte man auf die Idee kommen, auf den Link zum Algorithmus zu klicken. Ist man so weit gekommen, so muss man nur noch die Schlüsselwörter und Operatoren austauschen - imho auch für einen Anfänger trivial, sofern man die Basis-Kontrollstrukturen behandelt hat und kennt.
Nach obigen Code-Schnipsel zweifel ich eher genau daran, denn diese User-Interaktion verhilft einem irgend wie zu dem Eindruck, dass im Unterricht auf die falschen Dinge Wert gelegt wird.

[numerix]

Nach obigen Code-Schnipsel zweifel ich eher genau daran, denn diese User-Interaktion verhilft einem irgend wie zu dem Eindruck, dass im Unterricht auf die falschen Dinge Wert gelegt wird.

Verstehe ich nicht.

[sea-live]

Wir alle waren mal JUNG und da hat man wichtigeres zu tun als python zu Proggen
und bei WIKI zusuchen abgabe ist vermutlich morgen!

man kann ja mal die profie's fragen ob da was abfällt!
den sehn wir nichmehr wieder denn die suche nach GGt hat hier schon
die besten ergebnisse
zB

Code: Alles auswählen

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

[Hyperion]

Verstehe ich nicht.

Das hier habe ich schonmal, aber keine Ahnung wie ich es weiter machen soll:

Code: Alles auswählen

1
2
3
4
	
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 ")

Dies ist doch wirklich kein Anfang, um an das Problem ranzugehen! Ok, man braucht wohl als Input zwei Zahlen, aber das ist ja nun trivial und in dieser Form ja nicht einmal zwingend notwendig (und mit input statt raw_input auch noch fragwürdig ^^ ). Ein

Code: Alles auswählen

a = 1071
b = 1021

wäre wohl genauso effizient am Anfang

Entscheidend ist doch dabei, dass so eine triviale Userinteraktion evtl. als aller aller erste Motivation mal doll sein kann, aber ja per se nichts zur Lösung solch eines Problem beiträgt bzw. imho nicht einmal als Lösungsansatz gewertet werden kann.

Naja wird jetzt leicht offtopic, aber irgend wo muss so was ja her kommen. Also entweder hat er sonst nichts kapiert und in der Schule abgeschaltet und daher mal diesen "Ansatz" hier gepostet, oder aber dieses Vorgehen ist wirklich in der Schule so vermittelt worden. Vielleicht sehe ich aber auch zu schwarz und stehe mit meiner Meinung alleine da

[Hyperion]

Wir alle waren mal JUNG und da hat man wichtigeres zu tun als python zu Proggen
und bei WIKI zusuchen abgabe ist vermutlich morgen!

Hm ... naja, also dann hat er doch eigentlich NICHTS wichtigeres zu tun, als dieses Problem zu lösen? Aber ok, das führt jetzt zu weit offtopic

man kann ja mal die profie's fragen ob da was abfällt!

Hat er doch auch - wo ist da jetzt das Problem?

den sehn wir nichmehr wieder denn die suche nach GGt hat hier schon
die besten ergebnisse
zB

Code: Alles auswählen

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

Wobei er ja dennoch vermutlich zuerst gepostet hat, ohne zu suchen und ohne den angepinnten Thread zu lesen Und bevor ich mich in nem Python Forum anmelde, würd ich schon mal ein wenig googlen!

Mein Gott, was hatten wir es damals ohne Internt noch schwer in der Schulde

[Ghost]

Ich hatte nun insgesamt 4 Stunden Programmierunterricht.
Vorher noch nie was von der Programmiersprache gehört.
Und nein morgen ist kein Abgabetermin, diese Aufgabe war freiwillig und ich mache sie aus eigendem Interesse.

[numerix]

Verstehe.

Ich würde allerdings nicht aufgrund dieses Ansatzes eines Schülers auf die Qualität des Unterrichts schließen wollen. Ghost hat zumindest verstanden, dass er zwei Werte eingeben muss. Die Sache mit dem input() finde ich auf dieser Ebene des Lernens absolut unproblematisch - das müssen wir aber hier nicht zum x-ten Male durchkauen. Hat sich demnächst mit Py3000 eh erledigt.

Dass Ghost nicht weiterkommt, als bis zu dem, was er bisher gezeigt hat, ist wahrhaft keine große Tat. Aber, naja, vielleicht ist bei ihm das Programmieren einfach mehr ein MUSS als eine Herzensangelegenheit. Und nicht jedem ist das algorithmisch-problemlösende Denken in die Wiege gelegt.

Vielleicht zeigt er uns ja noch selbst entwickelten Code zur Erzeugung einer Liste aller Teiler einer Zahl. Und dann mal weiter sehen. Der rekursive Euklid von sea-live dürfte Ghost auf seiner momentanen Ebene des Verstehens kein bisschen weiterhelfen.

[Ghost]

hier mal ein weiterer schritt.
Müsste so in Ordnung sein 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 ")


if zahl1 > zahl2:
         teiler = zahl1 % zahl2
         print teiler
else:
         teiler = zahl2 % zahl1
         print teiler

nun sortiert er ja schonmal die beiden Zahlen der größe nach.
und rechnet den rest aus

[numerix]

Du müsstest dich dann mal entscheiden, ob du deinen ursprünglichen Ansatz mit den Teilermengen weiterverfolgen willst, oder nun doch auf den euklidischen Zug aufspringst (so sieht dein "fortgeführter Ansatz" nämlich aus).

In jedem Fall brauchst du doch mal eine Schleife, weil es ein Prozess des fortgesetzten Dividierens ist.

[Ghost]

Hi,
ich habe vor nun auf den euklidischen Zug aufzuspringen.

Ja, genau bei schleifen liegt mein Problem. Diese habe ich noch nicht so ganz verstanden.

wir haben bisher einmal ganz kurz die while schleife angesprochen.

aber wie muss ich diese while schleife da nun genau einbringen?

vllt. so?

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 ")

while(teiler == 0):
 if zahl1 > zahl2:
         teiler = zahl1 % zahl2
         print teiler
 else:
         teiler = zahl2 % zahl1
         print teiler

[numerix]

Dein Problem sind nicht nur die Schleifen - da liegt noch Grundlegenderes im Argen.

Wenn es tatsächlich so sein sollte, dass Schleifen "nur ganz kurz angesprochen wurden", dann solltest du - oder gemeinsam mit anderen - den Lehrer vielleicht bitten, das noch einmal zu erklären.

Schreib doch zunächst mal ein Programm, dass von 1 bis 100 zählt und die Zahlen ausgibt. Bekommst du das hin? Wenn nein, dann vergiss das mit dem ggT erstmal.