Ich habe versucht, die folgende Formel zu verwenden
Um den Index einer Fibonacci-Zahl zu finden () in einer Programmierfrage und alle kleineren Testfälle bestanden, aber einige Fälle, in denen F nahe 10 ^ 18 lag, schlugen fehl. Ich habe einen Probelauf durchgeführt und festgestellt, dass bei F = 99194853094755497 (82. Fibonacci-Zahl) der Wert von n gemäß der obigen Formel 81 ist. Ich habe dies in Python und C ++ codiert, das hier und hier jeweils. Ich möchte wissen, ob die Formel für jeden Wert von F funktioniert oder einige Einschränkungen aufweist.
Hinweis: Nach weiteren Tests stellte ich fest, dass der Code bis zur 52. Fibonacci-Zahl die richtigen Antworten liefert.
Update: Die Frage hat keine Testfälle, deshalb habe ich eine for-Schleife verwendet. Die angegebene Zahl F muss nicht unbedingt eine Fibonacci-Zahl sein. Wenn zum Beispiel F = 6 ist, dann liegt es zwischen zwei Fibonacci-Zahlen 5 und 8. Jetzt ist der Index von '5' in der Fibonacci-Sequenz 4, also ist die Antwort 4.
3 Antworten
Die Formel funktioniert gut:
import math
n = 99194853094755497
print math.log(n * math.sqrt(5) + 0.5) / math.log(1.61803398875) - 1
Ausgabe:
82.0
Eine Bemerkung zu Ihrem Code:
- Die Verwendung von
int(...)zum Runden auf eine Ganzzahl kann zu Problemen führen, wenn das Gleitkommaergebnis sehr nahe an82.0liegt. Numerische Probleme können dazu führen, dass es etwas größer ist, obwohl es mathematisch kleiner wäre.
F = 99194853094755497 ist 84 Fibonacci-Zahl und daher ist der Index dafür 83. Verwenden Sie das folgende Skript, um den richtigen Index zu erhalten (Ganzzahl statt Gleitkomma).
eps = 10**-10
phi = (1+math.sqrt(5))/2 # golden search ratio
fibonacci_index = int(round(math.log(n * math.sqrt(5)+eps)/math.log(phi)))
Zusätzliche Informationen, Code Siehe dies https://github.com/gvavvari/Python/tree/master/Fibonacci_index für eine detailliertere Dokumentation zur Implementierung
Ich denke, Ihre Formel verursacht einen Stapelüberlauf, weil die Anzahl zu groß ist, um int zu halten.