Einfach 0 gelöst 0% Erfolgsquote

Lucas Numbers

Return the nth Lucas number, the Fibonacci-like sequence that starts 2, 1.

Das lernst du

  • Compute a Fibonacci-like sequence
  • Use the right starting values
  • Avoid computing one term past the answer

Problem

Übersetzung anzeigen

The Lucas numbers follow the same rule as the Fibonacci numbers, each term being the sum of the two before it, but they start differently: L(0) = 2 and L(1) = 1. The sequence goes 2, 1, 3, 4, 7, 11, 18, 29, …

Implement lucas_numbers(n).

Input

n: The index of the term, starting at 0.

Output

Return L(n).

Einschränkungen

0 ≤ n ≤ 90

Beispiele

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

The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.

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

The sequence starts with L(0) = 2.

So gehst du vor

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

Hinweis 1

Keep the current and next terms in two variables.

Hinweis 2

The only difference from Fibonacci is the start: 2 and 1.

Hinweis 3

For n = 90 the next term would not fit in 64 bits, so stop the loop at n.

Erwartete Komplexität

O(n) time, O(1) extra space

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.