Primfaktorzerlegung!? Hilfe!

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.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

@autos: ich habe Python auch nur durch OnlineTutorials, durch dieses Forum und durch reine Neugierde gelernt.

Python bringt dafuer auch alles mit. Die Grundlagen findest du im Tutorial auf python.org, als Spielwiese hast du den Interpreter, der direkt ausfuehrbar ist, und Fragen zu einzelnen Details hast du beim Interpreter eine help()-Funktion. Was will man mehr??
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
BlackJack

@Groucho: Wenn Du die Liste sowieso immer durchreichst, dann hast Du eine iterative Lösung geschrieben, nur undurchschaubarer, langsamer und komplizierter als wenn man es gleich mit einer Schleife geschrieben hätte.

Rekursive Lösungen bieten sich immer an, wenn man eine grosses Problem in kleinere gleichartige Probleme zerlegen kann, die unabhängig voneinander gelöst werden und dann wieder zu einer Gesamtlösung zusammengefügt werden können. Hier braucht die Lösung jedes Teilproblems aber die Lösung vom vorhergehenden, d.h. das Lösen der einzelnen Teilprobleme geschieht wiederholt nacheinander. Also eigentlich in einer Schleife.
Groucho
User
Beiträge: 9
Registriert: Donnerstag 15. Februar 2007, 14:44

@BlackJack: Da hast Du natürlich recht: Ich dachte zuerst, ich gewinne etwas durch die Rekursion, weil ich die zerlege-Funktion nach dem Aufinden eines Faktors mit Parameter zahl/faktor statt mit zahl aufrufen kann und die Prüfung dann nur bis zu sqrt(zahl/faktor) statt bis sqrt(zahl) laufen muss.

Das kann ich aber genauso in der iterativen Variante berücksichtigen und die ist dann natürlich schneller als die rekursive. :)
Groucho
User
Beiträge: 9
Registriert: Donnerstag 15. Februar 2007, 14:44

Nochmal zum Thema rekursive vs. iterative Lösung:

Das Grundproblem ist meines Erachtens rekursiv: Hat man nämlich einen faktor von zahl gefunden, so ist [Zerlegung von zahl] = [faktor] + [Zerlegung von zahl/faktor]. Für zahl/faktor braucht man auch nur noch die Teiler ab factor prüfen, die kleineren sind ja schon erledigt.

Das Problem ist also auf ein gleichartiges einfacheres Problem reduziert, wobei die Rekursion terminiert, wenn die noch zu prüfende Zahl eine Primzahl ist.

Hier eine echte rekursive Lösung (ohne Durchreichung der Ergebnisliste :oops:):

Code: Alles auswählen

from math import sqrt

def zerlege_rekursiv(zahl,start_faktor=2):
    if start_faktor <= sqrt(zahl): # wenn noch nicht am Ende
        if start_faktor == 2:   # zuerst auf Faktoren 2 prüfen
            if zahl%2 == 0:
                # Faktoren: [2] + [Faktoren von zahl/2]
                return ([2]+zerlege_rekursiv(zahl/2,2)) 
            else:
                start_faktor = 3

        # ungerade Zahlen von start_faktor bis sqrt(zahl) kommen
        # Teiler in Frage
        for faktor in xrange(start_faktor, int(sqrt(zahl))+1,2):
            if zahl % faktor == 0:
                # Faktoren: [faktor] + [Faktoren von zahl/faktor]
                # beginne dort bei faktor, kleinere Teiler schon geprüft
                return ([faktor] + zerlege_rekursiv(zahl/faktor,faktor))

    # verbleibende zahl ist prim -> selbst in Teilerliste aufnehmen
    return [zahl]
und hier die entsprechende iterative Lösung:

Code: Alles auswählen

def zerlege_iterativ(zahl):
    faktor_liste = []
    
    while zahl % 2 == 0: # zuerst auf Faktoren 2 prüfen 
        zahl /= 2
        faktor_liste.append(2) 
    if zahl>1:          # wenn nicht nicht am Ende
        faktor = 3      # ungerade Zahlen ab 3 als Teiler prüfen
        upperlimit = sqrt(zahl) # Obergrenze ist sqrt(zahl)

        while faktor <= upperlimit:
            while zahl % faktor == 0: # wenn Teiler gefunden
                faktor_liste.append(faktor)
                zahl/= faktor          # nur noch zahl/faktor prüfen
                upperlimit = sqrt(zahl) # und neue Obergrenze beachten
            faktor += 2

        if zahl>1:  # verbleibende zahl ist prim -> selbst aufnehmen
           faktor_liste.append(zahl)
    return (faktor_liste)
Die iterative Lösung ist etwa 10% schneller, die (neue) rekursive aber leichter lesbar.

Code: Alles auswählen

from benchmark import Benchmark

def fiter(lower,upper):
    for i in xrange(lower,upper):
        zerlege_iterativ(i)

def frek(lower,upper):
    for i in xrange(lower,upper):
        zerlege_rekursiv(i)

lower = 20000
upper = 60000

bench = Benchmark()
bench.add_function(fiter, "iterativ", lower,upper)
bench.add_function(frek, "rekursiv", lower,upper)

bench.run()
bench.print_ranking()
benchmark.py aus http://paste.pocoo.org/show/83/ siehe http://www.python-forum.de/viewtopic.php?p=58861#58861

mit dem Ergebnis:
[Die Laufzeit wird ermittelt]
run: fiter - iterativ OK (1.19sec.)
run: frek - rekursiv OK (1.30sec.)

[Ranking wird erzeugt]
Ranking wurde erzeugt.
-------------------------------------------------------------------------------
Funktion: frek - rekursiv ist am langsamsten; Zeit: 1.301108 sec
Funktion: fiter - iterativ ist um 9.22% schneller; Zeit: 1.191261 sec
-------------------------------------------------------------------------------
BlackJack

Ich finde beide gleich (un)lesbar. Die rekursive Funktion hat den Nachteil, das Funktionsaufrufe teurer sind als Schleifen, das es ein Rekursionslimit gibt und das nach der Rückkehr von jedem rekursiven Aufruf die Liste einmal kopiert wird, nur um ein Element hinzuzufügen.
Antworten