Problema
Los números de Lucas siguen la misma regla que los de Fibonacci (cada término es la suma de los dos anteriores), pero empiezan de otra forma: L(0) = 2 y L(1) = 1. La sucesión es 2, 1, 3, 4, 7, 11, 18, 29, …
Implementa lucas_numbers(n).
Entrada
n: el índice del término, empezando en 0.
Salida
Devuelve L(n).
Restricciones
0 ≤ n ≤ 90
Ejemplos
Entrada:
n = 6
Salida esperada:
expected = 18
Entrada:
long long n = 6;
Salida esperada:
long long expected = 18;
Entrada:
long n = 6;
Salida esperada:
long expected = 18;
Explicación
Los términos son 2, 1, 3, 4, 7, 11, 18, así que L(6) = 18.
Entrada:
n = 0
Salida esperada:
expected = 2
Entrada:
long long n = 0;
Salida esperada:
long long expected = 2;
Entrada:
long n = 0;
Salida esperada:
long expected = 2;
Explicación
La sucesión empieza con L(0) = 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Guarda el término actual y el siguiente en dos variables.
Pista 2
La única diferencia con Fibonacci es el comienzo: 2 y 1.
Pista 3
Para n = 90 el término siguiente ya no cabría en 64 bits, así que detén el bucle en n.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.