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