Das deutsche Python-Forum

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

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

Code: Alles auswählen

def kgv(x, y):
    return x * y / ggt(x, y)

weil´s so schön war

r2d2

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

Hi

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

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

Gruss

rayo hat geschrieben:Hi

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

Wo liegt da das Problem?

Code: Alles auswählen

def größtergemeinsamerteiler(x, y):

@rayo

Code: Alles auswählen

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

sorry, ich konnte nicht anders.

r2d2

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

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

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.

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

modelnine hat geschrieben:Deswegen auch die "Schwanzrekursion." (wie sagt man dazu auf Deutsch?)

Endrekursion.

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?

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

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

DasIch hat geschrieben:Euch beiden ist schon klar dass der Thread schon über 2 Jahre alt ist?

D'oh ... ich hab den Thread einfach unter den seit dem letzten Besuch geposteten Beiträgen gesehen, und gar nicht weiter auf das Datum geachtet

Das deutsche Python-Forum

Größter gemeinsamer Teiler / kleinstes gem. Vielfaches

Größter gemeinsamer Teiler / kleinstes gem. Vielfaches