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
if
Anweisungen entfernen , indem ich die bedingten Ausdrücke in for-Schleifen verschiebe, aber das wäre meiner Meinung nach nur ein völlig nutzloser Hack.Antworten:
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 .nth Fn
Erinnern Sie sich an die Definition,
Wir könnten dies naiv mit einer rekursiven Funktion berechnen, die in Python definiert ist als:
Durch mehrmaliges Neuberechnen desselben Unterproblems benötigt diese Funktion jedoch exponentielle Zeit für die Berechnung (siehe Abbildung unten)!![fibtree](https://i.stack.imgur.com/ic61D.png)
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 .Fi Fn ![fib2](https://i.stack.imgur.com/bj1cc.png)
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) Fn O(n) Fi O(1) Fi Fi−1 Fi−2
quelle
Wenn Sie nur eine for-Schleife verwenden müssen, die iteriert, bis die n-te Fibonacci-Zahl gefunden wird, können Sie Folgendes verwenden:
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).
quelle