Einfach 3 gelöst 100.0% Erfolgsquote

Fibonacci-Zahl

Gib die n-te Fibonacci-Zahl zurück.

Das lernst du

  • Eine Folge aus ihren vorherigen Gliedern erzeugen
  • Zwei Variablen gleichzeitig aktualisieren
  • Sehen, warum naive Rekursion langsam ist

Problem

Die Fibonacci-Folge beginnt mit 0, 1 und jede weitere Zahl ist die Summe der beiden vorherigen: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 und F(1) = 1.

Implementiere fibonacci(n).

Eingabe

n: Die Position in der Folge.

Ausgabe

Gib F(n) zurück.

Einschränkungen

0 ≤ n ≤ 90

Beispiele

Beispiel 1
Eingabe:
n = 10

Erwartete Ausgabe:
expected = 55
Eingabe:
long long n = 10;

Erwartete Ausgabe:
long long expected = 55;
Eingabe:
long n = 10;

Erwartete Ausgabe:
long expected = 55;

Erläuterung

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.

Beispiel 2
Eingabe:
n = 0

Erwartete Ausgabe:
expected = 0
Eingabe:
long long n = 0;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long n = 0;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

Per Definition gilt F(0) = 0.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Die ersten beiden Werte sind fest, also beginne mit den Basisfällen.

Hinweis 2

Bilde spätere Werte aus den zwei vorherigen, statt sie rekursiv neu zu berechnen.

Hinweis 3

Nutze einen iterativen Ansatz, um doppelte Arbeit und tiefe Rekursion zu vermeiden.

Erwartete Komplexität

Zeit O(n), zusätzlicher Speicher O(1)

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.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 774 ms - 4/5 Code ansehen
2 KKKaneki Ken Python 858 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.