Maximalen Parameter einer Funktion herrausfinden

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
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

Hallo an alle :-),

ich möchte gerne für die Funktionen fib1(n), fib3(n), fib5(n) den maximalen Parameter n herrausfinden, bzw bis zu einer Zeit von 10s.
Hat jemand eine Idee dafür?
Mit dem Aufruf der Funktion "fib1_test(0)" bekam ich abn n=496 die Fehlermeldung: "RuntimeError: maximum recursion depth exceeded", wenn
ich aber "fib1(497)" aufrufe funktioniert es doch. Warum dann über den Aufruf in der Schleife nicht?

Code: Alles auswählen

def fib1(n):                      # Funktion berechnet die n-te Fibonacci-Zahl
    if n <= 1: 
         return n                     # Rekursionsabschluss
    return fib1(n-1) + fib1(n-2)      # Baumrekursion
#funktioniert bis n=496. Bei n=497


def fib3(n):
    f1, f2 = fib3Impl(n)    # Hilfsfunktion, f1 ist die Fibonacci-Zahl von (n+1) und f2 ist die Fibonacci-Zahl von n
    return f2

def fib3Impl(n):
    if n == 0: 
        return 1, 0         # gebe die Fibonacci-Zahl von 1 und die davor zurück
    else:                          # rekursiver Aufruf
       f1, f2 = fib3Impl(n-1)      # f1 ist Fibonacci-Zahl von n, f2 die von (n-1)
       return f1 + f2, f1          # gebe neue Fibonacci-Zahl fn+1 = f1+f2 und die vorherige (fn = f1) zurück.



def fib5(n):
    f1, f2 = 1, 0                # f1 ist die Fibonaccizahl für n=1, f2 die für n=0
    while n > 0:
        f1, f2 = f1 + f2, f1     # berechne die nächste Fibonaccizahl in f1 und speichere die letzte in f2
        n -= 1
    return f2

def fib1_test(z):
    z+=1
    print z, ":"
    print fib1(z)
    fib1_test(z)

def fib3_test(z):
    z+=1
    print z, ":"
    print fib3(z)
    fib3_test(z)

def fib5_test(z):
    z+=1
    print z, ":"
    print fib5(z)
    fib5_test(z)
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Hallo,

das hat nichts mit dem Wert der Parameter an sich zu tun sondern, wie die Fehlermeldung schon sagt, mit der Anzahl der Rekursionen. Python hat hier ein festes Limit, weshalb man mit rekursiven Lösungen sparsam umgehen sollte. Übersetze einfach die Rekursion in eine Schleife und schon bist du das Problem los.
Das Leben ist wie ein Tennisball.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Alternativ benutze die Formel für die direkte Berechnung einer Fibonacci-Zahl :-)
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

Vielen Dank für die schnellen Antworten.
Ich habe die Berechnungen absichtlich so gewählt, um die Geschwindigkeit bzw die Maxima von n herrauszufinden :-).
Gut also scheitert fib1 und fib3 weil die grenze der Rekursionen erreicht ist.
Wie könnte man herrausfinden welche Berechnungen unter 10s bleiben?
Ich kann ja schlecht einzelne Aufrufe über timeit machen, das würde doch ewig dauern :? :?:
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Das Stichwort lautet Bisektion.
Das Leben ist wie ein Tennisball.
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

Also ausprobieren? Noch andere Ideen?
BlackJack

@paupau90: Nein, wenn Du wissen willst wie lange etwas läuft, dann musst Du es schon wohl oder übel laufen lassen. Man könnte `multiprocessing` nehmen, weil man dann Prozesse die nach 10 Sekunden noch kein Ergebnis geliefert haben, killen kann.
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

Wenn ich mit

Code: Alles auswählen

t1 = timeit.Timer("fib1(9)", "from __main__ import fib1")
print t1.timeit()
teste, kommt eine Zeit raus, die viel länger ist, als wenn ich nur fib1(9) aufrufe(Schätzung).
Oder verstehe ich die Ausgabe falsch? Was bedeutet die Ausgabe 11.5197681459? 11.5 Sekunden?
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

Verstehe ich die Ausgabe falsch? Was bedeutet die Ausgabe 11.5197681459 des timeit Moduls? 11.5 Sekunden?
BlackJack

@paupau90: Schau doch einfach mal welche Argumente die `timeit()`-Methode entgegennimmt. Und in der Dokumentation steht auch das der Rückgabewert die Zeit in Sekunden ist.
paupau90
User
Beiträge: 26
Registriert: Sonntag 4. Mai 2014, 16:32

So dann hab ich leider noch eine Frage. Ich konnte leider nirgendwo finden, was es bedeutet, wenn ich Zahlen mit einem L am Ende bekomme.
Bsp:548931L
BlackJack

@paupau90: Das ist der Datentyp `long`. Wie `int` nur dass `long`-Werte beliebig gross werden können. Da Operationen auf `int`-Werten automatisch Ergebnisse vom Typ `long` liefern, ist diese Unterscheidung in 99,9% der Fälle irrelevant für den Programmierer.

Edit:

Code: Alles auswählen

In [22]: sys.maxint
Out[22]: 2147483647

In [23]: sys.maxint + 1
Out[23]: 2147483648L

In [24]: type(sys.maxint)
Out[24]: int

In [25]: type(sys.maxint + 1)
Out[25]: long
Antworten