Facile 0 résolus 0 % de réussite

Lucas Numbers

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

Ce que vous allez apprendre

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

Problème

Afficher la traduction

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

Contraintes

0 ≤ n ≤ 90

Exemples

Exemple 1
Entrée :
n = 6

Sortie attendue :
expected = 18
Entrée :
long long n = 6;

Sortie attendue :
long long expected = 18;
Entrée :
long n = 6;

Sortie attendue :
long expected = 18;

Explication

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

Exemple 2
Entrée :
n = 0

Sortie attendue :
expected = 2
Entrée :
long long n = 0;

Sortie attendue :
long long expected = 2;
Entrée :
long n = 0;

Sortie attendue :
long expected = 2;

Explication

The sequence starts with L(0) = 2.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Keep the current and next terms in two variables.

Indice 2

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

Indice 3

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

Complexité attendue

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

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.