Einfach 0 gelöst 0% Erfolgsquote

Tribonacci-Zahlen

Gib die n-te Tribonacci-Zahl zurück. Jedes Glied ist die Summe der drei vorherigen.

Das lernst du

  • Eine Folge iterativ berechnen
  • Nur die letzten paar Glieder aufbewahren
  • Die Anfangsglieder direkt behandeln

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

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

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

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.