Bestimmen, ob eine Zahl eine Fibonacci-Zahl ist

Lesen Sie den Abschnitt "Erkennen von Fibonacci-Zahlen" auf wikipedia .

  

Alternativ ist eine positive ganze Zahl z genau dann eine Fibonacci-Zahl, wenn eine von 5z ^ 2 + 4 oder 5z ^ 2 - 4 ein perfektes Quadrat ist. [17]

Alternativ können Sie weiterhin Fibonacci-Zahlen erzeugen, bis eine Ihrer Zahlen entspricht: Wenn dies der Fall ist, ist Ihre Nummer eine Fibonacci-Nummer. Wenn nicht, werden die Zahlen eventuell größer als Ihre Zahl und Sie können aufhören. Dies ist jedoch ziemlich ineffizient.

Wenn ich richtig verstehe, was Sie tun müssen (anstatt die ersten n Fibonacci-Zahlen auszugeben), müssen Sie bestimmen, ob n eine Fibonacci-Zahl ist.

Sie sollten also Ihre Methode so ändern, dass die Fibonacci-Folge solange erzeugt wird, bis Sie eine Zahl & gt; = n erhalten. Wenn es gleich ist, ist n eine Fibonacci-Zahl, andernfalls nicht.

Update: Von @ Morons wiederholten Behauptungen über den formelbasierten Algorithmus, der in der Leistung dem oben genannten überlegen ist, habe ich einen Benchmark-Vergleich gemacht - konkret zwischen Jacopos Lösung als Generatoralgorithmus und StevenHs letzte Version als formelbasierter Algorithmus . Als Referenz finden Sie hier den genauen Code:

Die Ergebnisse haben mich selbst überrascht:

Kurz gesagt, der Generator-Algorithmus übertrifft die formelbasierte Lösung bei allen positiven int-Werten - sogar nahe dem maximalen int-Wert ist er mehr als doppelt so schnell! So viel zur glaubensbasierten Leistungsoptimierung ;-)

Wenn der obige Code geändert wird, um long Variablen statt int zu verwenden, wird der Generatoralgorithmus langsamer (wie erwartet, da er jetzt long Werte addieren muss), und der Übergabepunkt ist der Formel beginnt schneller zu sein ist etwa 1000000000000L, dh 10 ¹² .

Update2: Wie IVlad und Moron schon gesagt haben, bin ich kein Experte in Fließkomma-Berechnungen :-) Aufgrund ihrer Vorschläge habe ich die Formel dahingehend verbessert:

Dies hat den Übergabepunkt auf ca. 10 ⁸ (für die long version - der Generator mit int ist immer noch schneller für alle int-Werte). Kein Zweifel, dass das Ersetzen der Aufrufe von sqrt durch etwas, wie es von @Moron vorgeschlagen wird, den Übergabepunkt weiter nach unten drücken würde.

Mein (und Ivlads) Punkt war einfach, dass es immer einen Wendepunkt geben wird, unter dem der Generator-Algorithmus schneller ist. Behauptungen, welche besser sind, haben keine Bedeutung im Allgemeinen, nur in einem Kontext.

Anstatt den Index n zu übergeben, schreibe eine Funktion, die ein Limit akzeptiert, und erhalte die Fibonacci-Zahlen bis zu und einschließlich dieses Limits. Lassen Sie sie einen Booleschen Wert zurückgeben, je nachdem, ob sie das Limit erreicht oder überspringt, und Sie können dies verwenden, um zu überprüfen, ob dieser Wert in der Sequenz enthalten ist.

Da es sich um Hausaufgaben handelt, ist ein solcher Anstoß wahrscheinlich alles, was wir Ihnen geben sollten ...

Es gibt eine Reihe von Methoden, die verwendet werden können, um zu bestimmen, ob eine gegebene Zahl in der Fibonacci-Sequenz ist, von der eine Auswahl auf wikipedia .

In Anbetracht dessen, was Sie bereits getan haben, würde ich wahrscheinlich einen Brute-Force-Ansatz wie den folgenden verwenden:

1. Erzeuge eine Fibonacci-Nummer
2. Wenn es weniger als die Zielnummer ist, generiere das nächste Fibonacci und wiederhole
3. Wenn es die Zielnummer ist, dann Erfolg
4. Wenn es größer ist als die Zielnummer, dann failure.

Ich würde wahrscheinlich eine rekursive Methode verwenden, die einen aktuellen n-Wert (dh so, dass sie die n-te Fibonacci-Zahl berechnet) und die Zielnummer eingibt.