Problème
Les nombres de Lucas suivent la même règle que ceux de Fibonacci (chaque terme est la somme des deux précédents), mais ils ne partent pas des mêmes valeurs : L(0) = 2 et L(1) = 1. La suite commence par 2, 1, 3, 4, 7, 11, 18, 29, …
Implémentez lucas_numbers(n).
Entrée
n : l'indice du terme, à partir de 0.
Sortie
Renvoyez L(n).
Contraintes
0 ≤ n ≤ 90
Exemples
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
Les termes sont 2, 1, 3, 4, 7, 11, 18, donc L(6) = 18.
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
La suite commence par L(0) = 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Gardez le terme courant et le suivant dans deux variables.
Indice 2
La seule différence avec Fibonacci, ce sont les valeurs de départ : 2 et 1.
Indice 3
Pour n = 90, le terme suivant ne tiendrait pas sur 64 bits, donc arrêtez la boucle à n.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.