Ich suche nicht unbedingt nach einer Antwort, aber ich suche nach dem, was diese Frage verlangt. Haben Sie diese Frage für ein Interview gefunden, aber nicht sicher, was sie fragen?
Schreib-Funktion, die die Fibonacci-Sequenz durchläuft und zurückgibt der Index, der als Parameter übergeben wird.
Erstens können Sie Ihre mathematischen Basisinformationen über Fibonacci mit diesem Link aus dem Wiki aktualisieren. und sieh dir diese Formel an, um schnell zu berechnen. Und du kannst alles darüber in diesen Link .
Dies ist eine rekursive Funktion, um die n-te Fibonacci-Zahl zu berechnen und hat die Zeit O (2 ^ n):
%Vor%Berechnen der Sequenz
Sie könnten argumentieren, dass in Bezug auf die tatsächliche Berechnung der Werte der Fibonacci Sequenz auf einem Computer, Sie sind besser dran mit dem Original Wiederholungsbeziehung, f [n] = f [n-1] + f [n-2]. Ich bin geneigt zuzustimmen. Benutzen die direkte geschlossene Lösung für große n, müssen Sie ein beibehalten viel Präzision. Selbst mit 9 Nachkommastellen, fn≈round (0.723606798⋅ (1,618033989) n) ist beispielsweise nur gültig für bis zu n = 38 (beobachten Sie hier gegen hier ). Auch das Addieren von ganzen Zahlen ist viel weniger rechenintensiv und genauer als potenzieren a Symbolischer Bruch oder ein Fließkommawert
Das ist die bessere Idee, die n-te Fibonacci-Zahl zu berechnen und ist von O (n) Zeit:
%Vor%und dies ist der beste Weg, die n-te Fibonacci-Zahl zu berechnen und ist von O (log (n)) Zeit:
Wie Sie bereits vermuten, funktioniert das sehr ähnlich. Verwenden Sie die n-te Potenz der x * x -Matrix
Das ist leicht zu verstehen, wenn Sie diese Matrix mit dem Vektor
multiplizieren %Vor%was zu
führt %Vor%Die Matrix-Potenzierung kann in der Zeit O (log (n)) erfolgen (wenn x als konstant betrachtet wird).
Für die Fibonacci-Wiederholung gibt es auch eine geschlossene Formellösung, siehe hier Ссылка , suche nach Binets oder Moivres Formel .
und schau dir an: 1- n-te Fibonacci-Nummer in der sublinearen Zeit
Was mir scheint ist, dass Sie gebeten werden, die n-te Fibonacci-Nr. zurückzugeben, wobei n der übergebene Parameter ist. Sie können verschiedene Methoden anwenden, um diese Frage zu beantworten, während all diese Unterschiede in der zeitlichen Komplexität und Komplexität des Codes variieren.
Methode 1 (Rekursion verwenden) Eine einfache Methode, bei der es sich um eine direkte rekursive Implementierung der mathematischen Rekursionsrelation handelt.
%Vor%Zeitkomplexität: T (n) = T (n-1) + T (n-2) was exponentiell ist. Wir können beobachten, dass diese Implementierung viele wiederholte Arbeiten ausführt (siehe den folgenden Rekursionsbaum). Das ist also eine schlechte Implementierung für die n-te Fibonacci-Nummer.
%Vor%fib (2) fib (1) fib (1) fib (0) fib (1) fib (0) / \ fib (1) fib (0) Extra Space: O (n), wenn wir die Größe des Aufrufs des Function Calls betrachten, ansonsten O (1).
Methode 2 (Verwenden Sie die dynamische Programmierung) Wir können die wiederholte Arbeit vermeiden, die Methode 1 durch Speichern der Fibonacci-Zahlen, die bisher berechnet wurden.
%Vor%Zeitkomplexität: O (n) Extra Leerzeichen: O (n)
Methode 3 (raumoptimierte Methode 2) Wir können den in Methode 2 verwendeten Speicherplatz optimieren, indem wir die vorherigen zwei Zahlen nur speichern, weil wir damit nicht mehr die nächste Fibannaci-Nummer in Reihe bringen können.
%Vor%Zeitkomplexität: O (n) Extra Platz: O (1)
Methode 4 (Verwendung der Potenz der Matrix {{1,1}, {0,1}}) Dieses andere O (n) beruht auf der Tatsache, dass, wenn wir n multiplizieren die Matrix M = {{1,1}, {0,1}} zu sich selbst (mit anderen Worten Macht (M, n) berechnen), dann Wir erhalten die (n + 1) te Fibonacci-Zahl als Element in Zeile und Spalte (0, 0) in der resultierenden Matrix.
Die Matrixdarstellung gibt den folgenden geschlossenen Ausdruck für die Fibonacci-Zahlen:
%Vor%Zeitkomplexität: O (n) Extra Platz: O (1)
Methode 5 (Optimierte Methode 4) Das Verfahren 4 kann optimiert werden, um in der Zeitkomplexität O (Logn) zu arbeiten. Wir können eine rekursive Multiplikation durchführen, um Leistung (M, n) in der Prevous-Methode zu erhalten (ähnlich wie in diesem Post)
%Vor%Zeitkomplexität: O (Logn) Extra Space: O (Logn) wenn wir die Größe des Funktionsaufrufstapels betrachten, sonst O (1).
Treiberprogramm: int Haupt () { int n = 9; printf ("% d", fib (9)); getchar (); zurückgeben 0; }
Es ist eine sehr schlecht formulierte Frage, aber Sie müssen annehmen, dass sie nach der n th Fibonnaci-Zahl fragen, wobei n als Parameter zur Verfügung gestellt wird.
Zusätzlich zu allen von anderen aufgelisteten Techniken können Sie für n > 1 auch die Methode Golden Ratio , die schneller als jede iterative Methode ist. Aber wie die Frage sagt "lauf durch die Fibonacci-Sequenz" kann dies nicht qualifizieren. Sie würden sie wahrscheinlich auch zu Tode erschrecken.
Ich interpretiere die Frage anders ... bei einem number als Eingabe, was ist der index dieser Zahl in der Serie? z.B. input=5 , dann ist der Index 5 (bei der Sequenz ist 0 1 1 2 3 5 , wobei der Index mit 0 beginnt)
Dies ist der folgende Code (der den Index zurückgibt) [Haftungsausschluss: Angepasst von dem Code, der in Ссылка angegeben wurde ]
%Vor%