Größter gemeinsamer Teiler / kleinstes gem. Vielfaches

[r2d2]

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

[rayo]

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]

Code: Alles auswählen

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

weil´s so schön war

r2d2

[jens]

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

[rayo]

Hi

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

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

Gruss

[Python 47]

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

[r2d2]

@rayo

Code: Alles auswählen

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

sorry, ich konnte nicht anders.

r2d2

[rayo]

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]

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

[modelnine]

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.

[r2d2]

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

[BlackJack]

Deswegen auch die "Schwanzrekursion." (wie sagt man dazu auf Deutsch?)

Endrekursion.

[name]

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?

[lunar]

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]

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

[lunar]

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