Problem
Die Fibonacci-Folge beginnt mit F(1) = 1, F(2) = 1, und jedes weitere Glied ist die Summe der beiden vorherigen: 1, 1, 2, 3, 5, 8, 13, 21, ... Finde heraus, wo die Folge zum ersten Mal n Dezimalstellen erreicht. Die Glieder passen bald nicht mehr in 64-Bit-Ganzzahlen. Hat deine Sprache keine großen Ganzzahlen, addierst du sie als Ziffern-Arrays.
Implementiere fibonacci_with_n_digits(n).
Eingabe
n: Die Anzahl der Stellen.
Ausgabe
Gib den Index i des ersten Glieds F(i) mit mindestens n Stellen zurück. Für n = 1 ist die Antwort 1.
Einschränkungen
1 ≤ n ≤ 1000
Beispiele
Eingabe:
n = 2
Erwartete Ausgabe:
expected = 7
Eingabe:
long long n = 2;
Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long n = 2;
Erwartete Ausgabe:
long expected = 7;
Erläuterung
F(6) = 8 hat eine Stelle und F(7) = 13 hat zwei, also lautet die Antwort 7.
Eingabe:
n = 4
Erwartete Ausgabe:
expected = 17
Eingabe:
long long n = 4;
Erwartete Ausgabe:
long long expected = 17;
Eingabe:
long n = 4;
Erwartete Ausgabe:
long expected = 17;
Erläuterung
F(16) = 987 und F(17) = 1597, also lautet die Antwort 17.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Bewahre nur die letzten beiden Glieder auf.
Hinweis 2
Speichere jedes Glied als Ziffern und addiere mit Übertrag.
Hinweis 3
Zähle den Index mit, beginnend bei F(1) = 1.
Erwartete Komplexität
Zeit O(n²), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.