Problem
Die Tribonacci-Zahlen übertragen die Idee der Fibonacci-Folge auf drei Glieder: T(0) = 0, T(1) = 0, T(2) = 1, und ab dann gilt T(n) = T(n − 1) + T(n − 2) + T(n − 3). Die Folge lautet 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …
Implementiere tribonacci(n).
Eingabe
n: Der Index des Glieds, beginnend bei 0.
Ausgabe
Gib T(n) zurück. Man braucht immer nur die letzten drei Glieder, eine Schleife mit drei Variablen reicht also aus.
Einschränkungen
0 ≤ n ≤ 74
Beispiele
Eingabe:
n = 7
Erwartete Ausgabe:
expected = 13
Eingabe:
long long n = 7;
Erwartete Ausgabe:
long long expected = 13;
Eingabe:
long n = 7;
Erwartete Ausgabe:
long expected = 13;
Erläuterung
Die Glieder sind 0, 0, 1, 1, 2, 4, 7, 13, also ist T(7) = 13.
Eingabe:
n = 2
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 2;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 2;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
T(2) ist die erste 1 in der Folge: 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Gib die ersten drei Glieder direkt zurück.
Hinweis 2
Verwende drei Variablen und schiebe sie bei jedem Schritt eine Position weiter.
Hinweis 3
Eine rekursive Lösung ohne Zwischenspeicher wiederholt dieselbe Arbeit und ist viel zu langsam.
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.