Problem
Für die Lucas-Zahlen gilt dieselbe Regel wie für die Fibonacci-Zahlen: Jedes Glied ist die Summe der beiden vorherigen. Sie beginnen aber anders, nämlich mit L(0) = 2 und L(1) = 1. Die Folge lautet 2, 1, 3, 4, 7, 11, 18, 29, …
Implementiere lucas_numbers(n).
Eingabe
n: Der Index des Glieds, beginnend bei 0.
Ausgabe
Gib L(n) zurück.
Einschränkungen
0 ≤ n ≤ 90
Beispiele
Eingabe:
n = 6
Erwartete Ausgabe:
expected = 18
Eingabe:
long long n = 6;
Erwartete Ausgabe:
long long expected = 18;
Eingabe:
long n = 6;
Erwartete Ausgabe:
long expected = 18;
Erläuterung
Die Glieder sind 2, 1, 3, 4, 7, 11, 18, also ist L(6) = 18.
Eingabe:
n = 0
Erwartete Ausgabe:
expected = 2
Eingabe:
long long n = 0;
Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long n = 0;
Erwartete Ausgabe:
long expected = 2;
Erläuterung
Die Folge beginnt mit L(0) = 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Halte das aktuelle und das nächste Glied in zwei Variablen fest.
Hinweis 2
Der einzige Unterschied zu Fibonacci ist der Anfang: 2 und 1.
Hinweis 3
Für n = 90 würde das nächste Glied nicht mehr in 64 Bit passen, beende die Schleife also bei n.
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.