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

größter gemeinsamer Teiler (ggT) berechnen

Beitragvon Ghost » Dienstag 23. September 2008, 14:31

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
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Dienstag 23. September 2008, 14:35

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.
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Beitragvon name » Dienstag 23. September 2008, 14:40

Eine einfache Loesung waere eine schleife und der Modulo operator.
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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Re: größter gemeinsamer Teiler (ggT) berechnen

Beitragvon numerix » Dienstag 23. September 2008, 15:06

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

Beitragvon Ghost » Dienstag 23. September 2008, 15:26

@ EyDu,

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

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

Beitragvon numerix » Dienstag 23. September 2008, 15:32

Ghost hat geschrieben: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
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Dienstag 23. September 2008, 15:34

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

Beitragvon numerix » Dienstag 23. September 2008, 15:44

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

Beitragvon sea-live » Dienstag 23. September 2008, 18:03

wiki spukt das aus
Bild
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
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Dienstag 23. September 2008, 18:37

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

Beitragvon numerix » Dienstag 23. September 2008, 18:40

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

Beitragvon sea-live » Dienstag 23. September 2008, 18:44

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

Beitragvon Hyperion » Dienstag 23. September 2008, 18:51

numerix hat geschrieben:Verstehe ich nicht. :?:

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

Beitragvon Hyperion » Dienstag 23. September 2008, 18:54

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

Beitragvon Ghost » Dienstag 23. September 2008, 19:23

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.
Zuletzt geändert von Ghost am Dienstag 23. September 2008, 19:33, insgesamt 2-mal geändert.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder