Fibonacci-Zahl

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).

n: Die Position in der Folge.

Gib F(n) zurück.

0 ≤ n ≤ 90

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;

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;

Per Definition gilt F(0) = 0.

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)

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.