Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Erste Fibonacci-Zahl mit n Stellen

Finde die Position der ersten Fibonacci-Zahl mit n Stellen.

Das lernst du

  • Zwei Ziffern-Arrays addieren
  • Fibonacci-Glieder ohne Überlauf erzeugen
  • Beim ersten Glied anhalten, das eine Bedingung erfüllt

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.