Größter gemeinsamer Teiler / kleinstes gem. Vielfaches

Code-Stücke können hier veröffentlicht werden.
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Freitag 10. März 2006, 16:38

Code: Alles auswählen

def ggt(x, y):
    return not y and x or ggt(y,x%y)
weil es spass macht

r2d2

*edit ggt statt ggt2

EDIT (jens): Titel geändert
Zuletzt geändert von r2d2 am Freitag 10. März 2006, 17:51, insgesamt 1-mal geändert.
äh, nimm diese schlange von meinem hals.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 10. März 2006, 17:03

Hi

noch ohne Rekursion:

Code: Alles auswählen

def ggt(x, y):
    while y != 0:
        x,y = y, x%y
    return x
Wenn du bei dir noch das ggt2 durch ein ggt ersetzt funktionierts auch

Gruss
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Freitag 10. März 2006, 17:53

Code: Alles auswählen

def kgv(x, y):
    return x * y / ggt(x, y)
weil´s so schön war

r2d2
äh, nimm diese schlange von meinem hals.
Benutzeravatar
jens
Moderator
Beiträge: 8483
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Freitag 10. März 2006, 18:19

Ihr lebt in einer Welt voller Buchstaben aber keiner Wörter, was?

Wer sicht noch fragt, was ggt oder kgv heißen soll:

Größter gemeinsamer Teiler

kleinstes gemeinsames Vielfaches

siehe auch:
http://de.wikipedia.org/wiki/Gr%C3%B6%C ... Vielfaches

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 10. März 2006, 19:04

Hi

Ich darf ja auch keine Abstände in den Variablennamen haben :lol:

Im Ernst, danke Jens für die Mühen.

Gruss
Python 47
User
Beiträge: 574
Registriert: Samstag 17. September 2005, 21:04

Freitag 10. März 2006, 19:13

rayo hat geschrieben:Hi

Ich darf ja auch keine Abstände in den Variablennamen haben :lol:
Wo liegt da das Problem?

Code: Alles auswählen

def größtergemeinsamerteiler(x, y):
mfg

Thomas :-)
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Freitag 10. März 2006, 19:33

@rayo

Code: Alles auswählen

def ggt(x, y):
    while y:
        x,y = y, x%y
    return x
sorry, ich konnte nicht anders.

r2d2
äh, nimm diese schlange von meinem hals.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 10. März 2006, 19:46

Hi

Ach kein Problem, bei solchen "Optimierungen" halt ich mich gerne zurück.
Für mich ist es einfacher zu lesen wenn y != 0 steht. Da ist mir sofort klar, dass der euklidische Divisionsalgorithmus fertig ist wenn y == 0 ist.

Auch deine Version vom ggt hätte ich ein wenig anders gestaltet, weil es einfacher ist zu lesen.

Code: Alles auswählen

def ggt(x, y):
    if y == 0:
        return x
    else:
        return ggt(y,x%y)
Habe natürlich nichts gegen deine Version.

Gruss
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Freitag 10. März 2006, 20:50

ich habe einen ausflug in die welt der funktionalen programmierung gemacht – deswegen meine erste version von ggt.

ausserdem erfreue ich mich gerne an der schönheit der einzeiler.

andererseits habe ich natürlich nichts gegen selbsterklärende funktionen.

r2d2
äh, nimm diese schlange von meinem hals.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Freitag 10. März 2006, 20:56

ich habe einen ausflug in die welt der funktionalen programmierung gemacht
Deswegen auch die "Schwanzrekursion." ;-) (wie sagt man dazu auf Deutsch?)

Nur dass die bei Python eben nicht wegoptimiert wird, sprich das Programm ist echt rekursiv, was in einer funktionalen Programmiersprache im Normalfall zu einem iterativen Algorithmus geglättet wird (das geht bei tail-recursion). Deswegen würde ich dem Algorithmus von rayo sofort und unbedingt den Vorzug geben.
--- Heiko.
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Freitag 10. März 2006, 21:27

Code: Alles auswählen

def ggt(x, y):
    return not y and x or ggt(y,x%y)

def ggt1(x, y):
    if x > y:
        return ggt1(x-y, y)
    if x < y:
        return ggt1(x, y-x)
    if x == y:
        return x

def ggt2(x, y):
    while y:
        x,y = y, x%y
    return x

import time

def zeittest(func):
    t = time.clock()
    i = 0
    while i < 10000:
        # ggt[2,3](20,30)
        func(20,30)
        i += 1
    print time.clock() - t
    
print "ggt:",
zeittest(ggt)
print "ggt1:",
zeittest(ggt1)
print "ggt2:",
zeittest(ggt2)
ergibt:
ggt: 0.0214158802528
ggt1: 0.0171089022612
ggt2: 0.0146499270856

klar, die laufzeit spricht für die ggt2 variante.

r2d2
äh, nimm diese schlange von meinem hals.
BlackJack

Freitag 10. März 2006, 23:17

modelnine hat geschrieben:Deswegen auch die "Schwanzrekursion." ;-) (wie sagt man dazu auf Deutsch?)
Endrekursion.
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Mittwoch 18. März 2009, 21:32

modelnine hat geschrieben:Deswegen würde ich dem Algorithmus von rayo sofort und unbedingt den Vorzug geben.
Weil er in Python nicht optimiert wird und deswegen im Vergleich zu seinen iterativen Mitstreitern Ressourcen verschwendet?
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.
lunar

Donnerstag 19. März 2009, 00:12

jens hat geschrieben:Wer sicht noch fragt, was ggt oder kgv heißen soll:
Naja, wer sich das fragt, hätte mal irgendwo zwischen der siebten und der zehnten Klasse besser aufpassen sollen in Mathematik ;)
DasIch
User
Beiträge: 2478
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Donnerstag 19. März 2009, 00:33

Euch beiden ist schon klar dass der Thread schon über 2 Jahre alt ist? :wink:
Antworten