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
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 14. Februar 2007, 20:39

autos hat geschrieben:Learning By Doing wie soll man denn was doen, wenn der lehrer uns nicht mal die grundlagen erklären kann.

Das konnte mein Lehrer auch nicht. Hey, Moment, mein Lehrer hat mir gar kein Python beigebracht. Wenn ich so darüber nachdenke - ich hatte nicht einmal einen Informatik-Lehrer.

Python habe ich mir selbst beigebracht wie sicherlich eine Große Mehrheit der User hier. Scheint also durchaus möglich zu sein.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
autos
User
Beiträge: 4
Registriert: Mittwoch 14. Februar 2007, 08:09

Beitragvon autos » Freitag 16. Februar 2007, 16:46

hey leondias, du hattest denke ich ein paar hilfsmittel zum lernern, vielleicht ein buch. hast du ein buchtipp den auch wirklich eher minderbegabte verstehen?
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Beitragvon CM » Freitag 16. Februar 2007, 17:01

Bücher gibt es wie Sand am Meer - eine Suche hier im Forum würde Dir auch schon Hits geben. Ansonsten gibt es das [wiki=FAQ#WieFangeIchAlsEinsteigerAn]wiki[/wiki], das ein paar deutschsprachige Einsteigerinfos offeriert. Aber das offizielle Tutorial ist eigentlich auch schon sehr gut.

Gruß,
Christian
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Freitag 16. Februar 2007, 17:44

autos hat geschrieben:hey leondias

Bin zwar nicht leondias, aber da die Levenshtein-Distanz zu Leonidas nicht so groß ist antworte ich dennoch :roll:

autos hat geschrieben:du hattest denke ich ein paar hilfsmittel zum lernern, vielleicht ein buch.

Ich hatte VB6-Erfahrung (das VB-Wissen kann man zwar wegwerfen, aber Programmierwissen ist Programmierwissen). Für Lektüren kannst du mal [wiki]FAQ#DeutschsprachigeLektrenImNetz[/wiki] konsultieren. Ich selbst habe eine alte Ausgabe von Learning Python, aber ich habe Python hauptsächlich durch Online-Tutorials und Learning-by-doing gelernt, so dass ich das Buch selbst kaum gelesen habe.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Groucho
User
Beiträge: 9
Registriert: Donnerstag 15. Februar 2007, 14:44

Beitragvon Groucho » Sonntag 18. Februar 2007, 12:18

Für eine Primzahlzerlegung bietet sich eine rekursive Funkion an, weil das Problem sich nach dem Auffinden des ersten Faktor auf ein einfacheres Problem reduziert. Zum Beispiel

Code: Alles auswählen

from math import sqrt

def zerlege(zahl,start_faktor=2,faktor_liste=[]):
    if start_faktor <= sqrt(zahl):
        if start_faktor == 2:
            if zahl%2 == 0:
                return zerlege(zahl/2,2,faktor_liste+[2])
            else:
                start_faktor = 3
        for faktor in xrange(start_faktor, int(sqrt(zahl))+1,2):
            if zahl % faktor == 0:
                return zerlege(zahl/faktor,faktor,faktor_liste+[faktor])
               
    return faktor_liste +[zahl]

# zerlege Zahlen von 2 bis 30
for i in xrange(2,31):
    ergebnis = zerlege(i)
    if i == ergebnis[0]:
        print i, "ist prim"
    else:
        print i, "=", reduce(lambda a,b: str(a)+"*"+str(b),ergebnis)


Man müsste die zerlege-Funktion eigentlich auch schreiben können, ohne der Funktion eine Liste der bisher gefundenen Primfaktoren mitzugeben, aber ich sehe im Moment nicht wie.

Gruß, Groucho
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon nkoehring » Sonntag 18. Februar 2007, 13:01

@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??
BlackJack

Beitragvon BlackJack » Sonntag 18. Februar 2007, 14:15

@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

Beitragvon Groucho » Sonntag 18. Februar 2007, 17:56

@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

Beitragvon Groucho » Montag 19. Februar 2007, 16:47

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

Beitragvon BlackJack » Montag 19. Februar 2007, 17:35

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.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot], Google [Bot]