Das deutsche Python-Forum

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)

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.

Alternativ benutze die Formel für die direkte Berechnung einer Fibonacci-Zahl

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

Das Stichwort lautet Bisektion.

Also ausprobieren? Noch andere Ideen?

@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.

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?

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

@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.

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

@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

Das deutsche Python-Forum

Maximalen Parameter einer Funktion herrausfinden

Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden

Re: Maximalen Parameter einer Funktion herrausfinden