Ist es möglich, den n-ten Term einer Fibonacci-Sequenz unter Verwendung einer definitiven for-Schleife zu finden?

Ich verwende das Buch Einführung in die Informatik von John Zelle und werde am Ende von Kapitel 3 (Rechnen mit Zahlen) gebeten, den n-ten Term einer Fibonacci-Sequenz zu finden, wobei vermutlich eine definitive for-Schleife verwendet wird, wie keine andere Entscheidung Struktur wurde noch eingeführt.

Ist das möglich? Ich habe alles versucht, was mir einfiel.

** Ich weiß, wie man es mit if-Anweisungen und dergleichen löst. Aber das Buch hat noch keine Entscheidungsstrukturen behandelt, aber es fordert mich auf, den n-ten Begriff (vom Benutzer angegeben) zu finden. Ich kann also nur davon ausgehen, dass ich weiß, wie man dies mit "for" -Schleifen macht, da dies alles ist, was bisher behandelt wurde

Wenn es nur das dritte Kapitel ist, bezweifle ich, dass die Autoren die dynamische Programmierung behandelt haben, aber ich werde veranschaulichen, was passiert, wenn eine for-Schleife zur Berechnung der Fibonacci-Zahl .$n^\text{th}$$F_n$

Erinnern Sie sich an die Definition,

Wir könnten dies naiv mit einer rekursiven Funktion berechnen, die in Python definiert ist als:

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Durch mehrmaliges Neuberechnen desselben Unterproblems benötigt diese Funktion jedoch exponentielle Zeit für die Berechnung (siehe Abbildung unten)!

Es gibt jedoch eine Lösung. Wir können dynamische Programmierung verwenden, um eine "intelligentere" Rekursion durchzuführen und unsere vorherigen Ergebnisse beizubehalten. Auf diese Weise müssen wir F_i nicht neu . Unser Funktionsaufruf "Baum" wird zu einer Liste zusammenfallen und von unten nach oben berechnen . $F_i$$F_n$

def fib2(n):
    if n < 2:
        return n
    else:
        if not results[n]:
            results[n] = fib2(n - 1) + fib2(n - 2)
        return results[n]

Jetzt haben wir unseren , um zu berechnen , aber wenn Sie bemerken, benötigen wir zusätzlichen Platz (einen Punkt im Array für jedes ). Dies kann auf zusätzlichen Platz werden, da jedes nur zwei andere Fibonacci-Zahlen benötigt, nämlich und .$O(n)$$F_n$$O(n)$$F_i$$O(1)$$F_i$$F_{i-1}$$F_{i-2}$

def fib3(n):
    if n < 2:
        return n
    f_0 = 0
    f_1 = 1
    f_n = 0
    for _ in range(n - 1):
        f_n = f_0 + f_1
        f_0 = f_1
        f_1 = f_n


    return f_n

Wenn Sie nur eine for-Schleife verwenden müssen, die iteriert, bis die n-te Fibonacci-Zahl gefunden wird, können Sie Folgendes verwenden:

int fib(int n)
{
    int p = 0;
    int c = 1;
    int r = 0; // The result is initialized to 0 (undefined). 
    for (int i = 0; i < n; i++)
    {
        r = p + c; // Produce next number in the sequence.
        p = c;     // Save previous number.
        c = r;     // Save current number.
    }

    return r;
}

HINWEIS

In der obigen Lösung gehe ich davon aus, dass die Fibonacci-Sequenz 1 1 2 3 5 8 13 ... ist und dass n den Bereich 1, 2, 3, ... hat, da es unter diesen Annahmen keine Fibonacci-Zahl für n <1 gibt Die Funktion gibt eine 0 für n <1 zurück, um anzuzeigen, dass der Eingabeparameter außerhalb des Bereichs liegt (siehe Toms Vorschläge in den Kommentaren unten).