Was ist "billiger": Vertauschen oder noch eine Rek

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.
Antworten
hehejo
User
Beiträge: 56
Registriert: Freitag 18. Februar 2005, 18:24
Wohnort: Stein
Kontaktdaten:

Freitag 25. November 2005, 22:08

Was ist "günstiger"?
Im ersten Fall hab ich eine "Vertauschung" drin:
a, b = b, a
Ich weiß, dass da nichts vertauscht wird, sondern die Variablen a und b neu erstellt werden.

Code: Alles auswählen

def ggT(a,b):
        if a == b:
                return a
        if a > b:
                a,b = b,a
        return ggT(a,b-a)
Oder ist das hier klüger?
Anstatt zu "Vertauschen" wird ggT einfach mit vertauschten Werten aufgerufen. D.h. ich mach eine Rekursion mehr, bis ich zu dem Schritt komme, den ich gleich nach der "Vertauschung" im obigen Beispiel habe.

Code: Alles auswählen

def ggT(a,b):
        if a == b:
                return a
        if a > b:
               return(b, a)
        return ggT(a, b-a)
Gruß, Johannes
[b][color=red]ascii stupid question,
get stupid ansii[/color][/b]
[url]http://www.hehejo.de[/url]
SeB
User
Beiträge: 25
Registriert: Mittwoch 24. August 2005, 14:29
Wohnort: Buchenau/Hessen
Kontaktdaten:

Samstag 26. November 2005, 04:07

letzteres wird wohl nicht funktionieren, weil:

ggT(10,5) => (5, 10)

... oder hab ich da was verpeilt?
[url=http://therealzordak.de/index.php]therealzordak.de[/url] - [url=http://therealzordak.de/index.php?section=movies]Movies[/url] - [url=http://therealzordak.de/index.php?section=derwahn]Fun[/url]
BlackJack

Samstag 26. November 2005, 07:43

Zwei Namen an Werte binden ist auf jeden Fall "billiger" als ein Funktionsaufruf bei dem ja auch a und b an neue lokale Namen gebunden werden müssen plus allem was bei einem Funktionsaufruf so anfällt (Stackrahmen erstellen, hinspringen, Stackrahmen wieder abräumen, zurückspringen, etc.)

Da es sich hier um eine Endrekursion handelt wäre es das klügste es ganz ohne Rekursion zu machen. Und das ist in diesem Fall auch nicht so schwer.
helmut
User
Beiträge: 57
Registriert: Mittwoch 2. November 2005, 07:45
Wohnort: Dormagen

Samstag 26. November 2005, 08:24

Ich habe hier eine Version mit Rekursion, bei der die wiederholte Subtraktion durch Modulobildung abgekürzt wird:

Code: Alles auswählen

function ggt(a,b):
    if (b == 0):
        return a
    else:
        return ggt(b,a%b)
Helmut
hehejo
User
Beiträge: 56
Registriert: Freitag 18. Februar 2005, 18:24
Wohnort: Stein
Kontaktdaten:

Samstag 26. November 2005, 12:36

Mir ist schon klar, dass ich den ggT auch als normale Schleife hätte bauen können.
Aber ich habe genau die Antwort bekommen, die ich wollte: ab,bc ist "billiger" als ggT(b,a).

@SeB
Ja, da hast du wohl Recht. Mir ging's aber mehr um die Theorie.
Danke für dein scharfes Auge.
Gruß, Johannes
[b][color=red]ascii stupid question,
get stupid ansii[/color][/b]
[url]http://www.hehejo.de[/url]
BlackJack

Samstag 26. November 2005, 22:03

Noch eine praktische Anmerkung: Das Rekusrsionlimit kann mit Deinem `ggT()` ziemlich schnell erreicht werden. `ggT(10000, 5)` endet mit einer Ausnahme.
hehejo
User
Beiträge: 56
Registriert: Freitag 18. Februar 2005, 18:24
Wohnort: Stein
Kontaktdaten:

Sonntag 27. November 2005, 12:03

oh ja, das habe ich auch schon sehr schnell bemerkt, dass es bei solch extremen Werten schnell zum stackoverflow kommt.
Man könnte natürlich noch richtig viel optimieren, aber ich hab das ja eh nur geschrieben, um mir eine Aufgabe zu erleichtern.
Gruß, Johannes
[b][color=red]ascii stupid question,
get stupid ansii[/color][/b]
[url]http://www.hehejo.de[/url]
Antworten