Ich bin nicht auf der Suche nach einer Antwort, aber ich bin auf der Suche nach was diese Frage fragt. Haben Sie diese Frage bei einem Interview gefunden, wissen aber nicht genau, was sie fragen?Algorithmus-Funktion für Fibonacci-Serie
Schreib-Funktion, die durch die Fibonacci-Sequenz läuft und den Index zurückgibt, der als Parameter übergeben wird.
Erstens können Sie Ihre mathematischen Basisinformationen über Fibonacci mit dieser link aus Wiki aktualisieren. und schauen Sie sich this formula für schnelle Berechnung an. Sie können alles darüber in this link lesen.
Diese rekursive Funktion ist n-te Fibonacci-Zahl zu berechnen, und ist von O (2^n) Zeit:
int Fibonacci(int n) {
if (n == 0 || n == 1) return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2); }
der Sequenz
Computing Sie könnten, dass in Bezug auf die tatsächlich die Berechnung der argumentieren Werte der Fibonacci-Sequenz auf einem Computer, sind Sie besser dran mit der ursprünglichen Rekursionsbeziehung, f [n] = f [n-1] + f [n-2]. Ich bin geneigt zuzustimmen. Um die direkte geschlossene Lösung für große n zu verwenden, müssen Sie eine Menge Präzision pflegen. Auch bei 9 Nachkommastellen ist fn≈round (0,723606798⋅ (1,618033989) n) beispielsweise nur gültig für bis n = 38 (here gegenüber here beachten). Auch ganze Zahlen Zugabe ist viel weniger rechenintensiv und präziser als Potenzieren einen symbolischen Bruchteils oder ein Gleitkommawert
dies bessere Idee nth Fibonacci-Zahl zu berechnen, und ist O (n) Zeit:
int Fibonacci(int n) {
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;
int result = 0;
int preOldResult = 1;
int oldResult = 1;
for (int i=2;i<n;i++) {
result = preOldResult + oldResult;
preOldResult = oldResult;
oldResult = result;
}
return result;}
und dies ist der beste Weg, nth Fibonacci-Zahl zu berechnen, und ist von O (log (N)) Zeit:
Wie Sie bereits vermuten, wird dies sehr ähnlich funktionieren. Verwenden Sie die n-te Potenz der x * x Matrix
|1 0 0 0 .... 1 1|
|1
| 1
| 1
| 1
| 1
...................
...................
| ... 1 0|
Das ist leicht zu verstehen, wenn Sie diese Matrix mit dem
Vektor multiplizierenf(n-1), f(n-2), ... , f(n-x+1), f(n-x)
die
f(n), f(n-1), ... , f(n-x+1)
Matrix Potenzierung in Ergebnisse können in O (log (n)) Zeit durchgeführt werden (wenn x als konstant betrachtet wird).
Für das Fibonacci-Rezidiv gibt es auch eine geschlossene Formellösung, siehe hier http://en.wikipedia.org/wiki/Fibonacci_number, suche nach Binets oder Moivres Formel.
und Blick auf: 1- nth fibonacci number in sublinear time
Aus Ihrer Antwort eine CoffeeScript-Version: http://jsfiddle.net/3fe21mqm/ – nottinhill
public static int fibonacci(int i){
if(i==0)
return 0;
if(i==1)
return 1;
return fib(--i,0,1);
}
public static int fib(int num,int pre,int prepre){
if(num==0){
return prepre+pre;
}
return fib(--num,pre+prepre,pre);
}
interpretiere ich die Frage anders .... gegeben ein number als Eingabe, was ist die index diese Zahl in der Reihe? z.B. input=5, dann wird der Index 5 (angesichts der Sequenz 0 1 1 2 3 5 wird, wo beginnt der Index mit 0)
dies der Code ist wie folgt (die den Index zurückgibt) [Disclaimer: bei http://talkbinary.com/programming/c/fibonacci-in-c/ aus dem Code gegeben Angepasst]
int Fibonacci(int n)
{
if (n == 0)
return 0;
if (n== 1)
return 1;
int fib1 = 0;
int fib2 = 1;
int fib = 0;
int i = 0;
for (i = 2; ; i++)
{
fib = fib1 + fib2;
if (n == fib)
break;
fib1 = fib2;
fib2 = fib;
}
return i;
}
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, wobei sich all dies in der zeitlichen Komplexität und der Komplexität des Codes unterscheidet.
Methode 1 (Verwenden Sie Rekursion) Eine einfache Methode, die eine direkte recusive Umsetzung mathematische Reconcurance-Beziehung oben angegeben ist.
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
Zeitkomplexität: T (n) = T (n-1) + T (n-2), die Exponentialfunktion. 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.
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
FIB (2) FIB (1) FIB (1) FIB (0) FIB (1) FIB (0) /\ FIB (1) FIB (0) Extra Space: O (n) wenn wir die Bedeutung des Aufrufs betrachten, ansonsten O (1).
Methode 2 (Verwenden Sie die dynamische Programmierung) Wir können die wiederholte Arbeit vermeiden, ist die Methode 1 durch Speichern der Fibonacci-Zahlen, die bisher berechnet.
int fib(int n)
{
/* Declare an array to store fibonacci numbers. */
int f[n+1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Zeitkomplexität: O (n) Extra Space: O (n)
Methode 3 (Raum Otimized Methode 2) Wir können den Raum in Methode 2 durch Speichern der vorherigen zwei Zahlen verwendet optimieren nur weil wir nur noch die nächste Fibannaci-Nummer in Serie bekommen müssen.
int fib(int n)
{
int a = 0, b = 1, c, i;
if(n == 0)
return a;
for (i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
Zeitkomplexität: O (n) Extra Space: O (1)
Methode 4 (Verwendung Leistung des MATRX {{1,1}, {0,1}}) Diese ein anderes O (n), das auf der Tatsache beruht, dass, wenn wir n die Matrix M = {{1,1}, {0,1}} mit sich selbst multiplizieren (mit anderen Worten, die Leistung (M, n) berechnen), dann wir nimm die (n + 1) te Fibonacci-Zahl als Element in Zeile und Spalte (0, 0) in der resultierenden Matrix.
die Matrixdarstellung ergibt den folgenden geschlossenen Ausdruck für die Fibonacci-Zahlen:
/* Helper function that multiplies 2 matricies F and M of size 2*2, and
puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is desinged only for fib() and won't work as general
power function */
void power(int F[2][2], int n);
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n)
{
int i;
int M[2][2] = {{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
Zeitkomplexität: O (n) Extras Space: O (1)
Methode 5 (optimiertes Verfahren 4) Die Methode 4 kann optimiert werden, um in O (Logn) -Zeitkomplexität zu arbeiten. Wir können rekursiv Multiplikation tun, um Leistung (M, n) in dem prevous Verfahren (ähnlich wie bei der Optimierung in diesem Beitrag nicht getan) zu erhalten
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
if(n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if(n%2 != 0)
multiply(F, M);
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
Zeitkomplexität: O (Logn) Extras Space: O (Logn), wenn Wir betrachten die Funktion Call Stack Size, sonst O (1).
Treiberprogramm: int main() { int n = 9; printf ("% d", fib (9)); getchar(); Rückgabe 0; }
Referenzen: http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html
Es ist eine sehr schlecht formulierte Frage, aber man muss annehmen, dass sie für die n-te Fibonnaci Nummer fragen, wo n als Parameter vorgesehen ist.
Zusätzlich zu allen von anderen aufgelisteten Techniken können Sie für n > 1 auch die golden ratio method verwenden, 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.
Ah .... das machte es viel klarer. Danke. – KingKongFrog
Hast du meine Antwort gelesen? –
Angenommen, der Index _i_ ist angegeben. a) run through fib series: 1 1 (es sagt nicht wie weit oder wie weit, oder?) b) return _i_ – greybeard