Die Fibonacci-Sequenz ist durch die Rekursionsbeziehung definiert:
F
= F n-1 + F n-2, wobei F 1 = 1 und F 2 = 1. Also die ersten 12 Begriffe wird F 1 = F 1 = 2 F 3 = 3 F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, F10 = 55, F11 = 89, F12 = 144 Der 12. Term, F 12 , ist der erste Term, der drei Ziffern enthält.
Was ist der erste Ausdruck in der Fibonacci-Folge, der 1000 enthält? Ziffern?
Ich habe in Python eine Brute-Force-Lösung entwickelt, aber es dauert absolut ewig, die tatsächliche Lösung zu berechnen. Kann jemand eine Lösung ohne Brute-Force vorschlagen?
%Vor%Sie können eine Fibonacci-Funktion schreiben, die in linearer Zeit und mit konstantem Speicherbedarf läuft. Sie brauchen keine Liste, um sie zu behalten. Hier ist eine rekursive Version (wenn n jedoch groß genug ist, wird es nur stackoverflow )
%Vor%Diese Funktion ruft sich nur einmal auf (was zu N Aufrufen eines Parameters N führt), im Gegensatz zu Ihrer Lösung, die sich zweimal aufruft (etwa 2 ^ N ruft einen Parameter N auf).
Hier ist eine Version, die Stackoverflow nie und wird eine Schleife anstelle von Rekursion verwenden:
%Vor%Und das ist schnell genug:
%Vor% Aber fib aufzurufen, bis Sie ein Ergebnis erhalten, das groß genug ist, ist nicht perfekt: Die ersten Nummern der Serie werden mehrfach berechnet.
Sie können die nächste Fibonacci-Zahl berechnen und ihre Größe in der gleichen Schleife überprüfen:
Verwenden Sie Binets Formel . Es ist der schnellste Weg, um Fibonacci-Zahlen zu finden, und es verwendet keine Rekursion.
Zwei Dinge können mit einer kleinen Änderung in Ihrem Code sehr optimiert werden. Diese zwei Dinge sind:
Sie berechnen jede Fibonacci-Zahl mit zwei anderen Fibonacci-Zahlen, was zu einer exponentiellen Komplexität führt (die explodiert, selbst wenn Sie nur eine einzelne, aber hohe Fibonacci-Zahl berechnen würden).
Sie erinnern sich an keine vorher berechnete Fibonacci-Nummer, um die nächste in Ihrer Schleife zu berechnen.
Merken Sie sich einfach alle berechneten Fibonacci-Zahlen als privates Implementierungsdetail in Fibonacci und Sie werden beide Leistungsprobleme los. Sie können dies tun, indem Sie ein einfaches dynamisches Array verwenden, dem Sie das Ergebnis hinzufügen, wenn es zuvor nicht zwischengespeichert wurde.
Pseudocode (ich spreche kein Python, aber das kann leicht implementiert werden):
%Vor%Dies führt zu einer sehr eingeschränkten Rekursion, da Sie die N-te Fibonacci-Zahl nur dann berechnen, wenn Sie die (N-1) -te Nummer bereits kennen und zwischengespeichert haben.
Diese Optimierung funktioniert auch, wenn Sie any Fibonacci-Nummer brauchen (für zukünftige Probleme), aber in diesem speziellen Fall wissen wir, dass wir uns nur die letzten zwei Zahlen merken müssen, da wir nie dazu kommen werden Fragen Sie erneut nach alten Nummern. Sie brauchen also keine ganze Liste von Zahlen, sondern nur zwei, die Sie für jeden Schritt in Ihrer Hauptschleife durchlaufen. Etwas wie
%Vor%innerhalb der Schleife und eine Initialisierung wie
%Vor% ersetzt im Wesentlichen Ihre Funktion Fibonacci und ihre Leistungsprobleme, beschränkt Sie jedoch auf diesen eingeschränkten Anwendungsfall.
Sie können versuchen, die Newton-Approximationsmethode auf Binets Formel . Die Idee besteht darin, eine Tangente auf dem Graphen zu finden und den x-Achsenabschnitt dieser Linie zu verwenden, um den Wert der Nullstelle des Graphen zu approximieren.
Warum hat niemand dafür Generatoren benutzt? Dies ist eine Brute-Force-Lösung, aber es ist sehr schnell:
%Vor%Dies gibt einen Generator, der die Fibonacci-Sequenz berechnet. Zum Beispiel
%Vor%erzeugt
%Vor%Damit können wir das Problem so lösen:
%Vor%Dies erzeugt die Ausgabe
%Vor%Der Generator berechnet die Reihenfolge und erzeugt Terme 1 zu 1 und diese Lösung läuft fast sofort.
Anstatt jedes Terms jedesmal rekursiv zu berechnen, machen Sie ein Array von Termen, dann können Sie einen Term berechnen, indem Sie Terme [-1] und Terme [-2]
hinzufügenHier ist die Java-Version in konstantem Raum und linearer Zeit:
%Vor%Tags und Links python fibonacci brute-force