Betrachten Sie das folgende Code-Snippet:
%Vor% Vorausgesetzt, fib wird von main mit N als 10,35,67 aufgerufen, ... (sagen wir), wie viele Aufrufe insgesamt
werden zu fib ?
Gibt es eine Beziehung für dieses Problem?
PS: Das ist eine theoretische Frage und soll nicht ausgeführt werden.
BEARBEITEN:
Ich kenne andere Methoden für die schnellere Berechnung von Fibonacci-Reihen.
Ich möchte eine Lösung für die Berechnung der Anzahl der Male fib aufgerufen wird für fib (40), fib (50), .. ohne Hilfe des Compilers und in der Prüfungsbedingung, wo Sie 40 Frage ähnlich wie diese in beantworten sollen eine festgelegte Zeit (ca. 30 Minuten).
Danke,
Sei f (n) die Anzahl der Aufrufe, die zum Berechnen von fib(n) ausgeführt wurden.
Also ist f mindestens O (fib (n)) . Tatsächlich ist f (n) 2 * fib (n) - 1 . Wir zeigen dies durch Induktion:
Es gibt effiziente Wege , um einen Fibonacci-Begriff zu berechnen. Also gilt das Gleiche für f (n) .
Gibt es eine Beziehung für dieses Problem? ?
Es gibt eine Gleichung für die n-te Fibonacci-Zahl: Ссылка
In dem Pseudocode, den Sie gepostet haben, erfüllt die Anzahl der Aufrufe die Wiederholungsrelation
%Vor%Das ist fast dasselbe wie die Fibonacci-Rekursionsbeziehung. Beweis durch Induktion kann zeigen, dass die Anzahl der von fib (n) gemachten Anrufe zu fib gleich 2 * fib (n) -1 ist, für n & gt; = 0.
Natürlich kann die Berechnung beschleunigt werden, indem der Ausdruck in geschlossener Form verwendet wird, oder indem Code hinzugefügt wird, um zuvor berechnete Werte zu speichern.
Wie oben erwähnt, müssen Sie die folgende wiederkehrende Gleichung lösen: K (n) = K (n-1) + K (n-2) +1
Schreiben wir es für n-1: K (n-1) = K (n-2) + K (n-3) +1
Nun subtrahiere die zweite von der ersten: K (n) -K (n-1) = K (n-1) - K (n-3),
oder
K (n) - 2 · K (n-1) + K (n-3) = 0.
Die jeweilige charakteristische Gleichung lautet: x ^ 3 - 2 * x ^ 2 + 1 = 0.
Es hat die folgenden Wurzeln: 1, (1 + sqrt (5)) / 2, (1-sqrt (5)) / 2
Also für jedes reale A, B, C die folgende Funktion K (n) = A * (1) ^ n + B * ((1 + sqrt (5)) / 2) ^ n + C * ((1-sqrt (5)) / 2) ^ n
wird eine Lösung für Ihre Gleichung sein.
Um A, B, C zu finden, müssen Sie mehrere Anfangswerte K (0), K (1), K (2) definieren und das Gleichungssystem lösen.
phi ist eine Konstante
%Vor%n ist die Fibonacci-Nummer ... Position gibt Ihnen die Fibonacci-Nummer ist n
zum Beispiel gegeben 13, wird die Position 7 - 0 1 1 2 3 5 8 13
seinMit dieser Position berechnen Sie einfach die Fibonacci-Zahl an Position-1 oder eine beliebige Position relativ zur gegebenen Fibonacci-Zahl.
%Vor% floor((pow(phi, position)/sqrt(5))+0.5) - ist die Standardformel für die Berechnung von N-fibonacci num (Hinweis - Dies ist keine Näherung)
Ich habe gerade diese Formel umgedreht, um die Position zu berechnen und die Position - 1 zu verwenden, um die vorherige Fibonacci-Zahl zu berechnen.
Ref - Ссылка
Dies ist ein klassisches Problem bei der Lösung mit Wiederholungsbeziehungen .
Insbesondere hat das Fibonacci-Problem die folgenden Parameter:
%Vor% Sobald Sie das Lösen von Wiederholungen gemeistert haben, haben Sie kein Problem mehr, die Lösung zu erreichen (was übrigens genauso ist wie fib(n) ).
Interessante Frage, ich kann Ihnen keine Formel geben, aber ich habe ein Ruby-Programm dafür geschrieben, es arbeitet mit Zahlen, die ich auf dem Papier herausgefunden habe, und es sollte für alle funktionieren.
%Vor%.
%Vor%Es ist langsam .. Ich bin gerade dabei herauszufinden, 35 werde ich bearbeiten, wenn es fertig ist.
Bearbeiten:
%Vor%