Ich habe versucht, die folgende Formel zu verwenden

formula

Um den Index einer Fibonacci-Zahl zu finden (text) 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.

1
Shubham 20 Aug. 2015 im 22:21

3 Antworten

Beste Antwort

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 an 82.0 liegt. Numerische Probleme können dazu führen, dass es etwas größer ist, obwohl es mathematisch kleiner wäre.
1
Falko 20 Aug. 2015 im 20:12

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

-2
Gopi Vinod Avvari 27 Sept. 2016 im 20:17

Ich denke, Ihre Formel verursacht einen Stapelüberlauf, weil die Anzahl zu groß ist, um int zu halten.

-1
rottenbanana 20 Aug. 2015 im 19:33