@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??
Primfaktorzerlegung!? Hilfe!
- nkoehring
- User
- Beiträge: 543
- Registriert: Mittwoch 7. Februar 2007, 17:37
- Wohnort: naehe Halle/Saale
- Kontaktdaten:
[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
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
@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.
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.
@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.
Das kann ich aber genauso in der iterativen Variante berücksichtigen und die ist dann natürlich schneller als die rekursive.
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 ):
und hier die entsprechende iterative Lösung:
Die iterative Lösung ist etwa 10% schneller, die (neue) rekursive aber leichter lesbar.
benchmark.py aus http://paste.pocoo.org/show/83/ siehe http://www.python-forum.de/viewtopic.php?p=58861#58861
mit dem Ergebnis:
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]
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)
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()
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
-------------------------------------------------------------------------------
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.