Problema
Os números de Lucas seguem a mesma regra dos números de Fibonacci, em que cada termo é a soma dos dois anteriores, mas começam de outro jeito: L(0) = 2 e L(1) = 1. A sequência fica 2, 1, 3, 4, 7, 11, 18, 29, …
Implemente lucas_numbers(n).
Entrada
n: o índice do termo, começando em 0.
Saída
Retorne L(n).
Restrições
0 ≤ n ≤ 90
Exemplos
Entrada:
n = 6
Saída esperada:
expected = 18
Entrada:
long long n = 6;
Saída esperada:
long long expected = 18;
Entrada:
long n = 6;
Saída esperada:
long expected = 18;
Explicação
Os termos são 2, 1, 3, 4, 7, 11, 18, então L(6) = 18.
Entrada:
n = 0
Saída esperada:
expected = 2
Entrada:
long long n = 0;
Saída esperada:
long long expected = 2;
Entrada:
long n = 0;
Saída esperada:
long expected = 2;
Explicação
A sequência começa com L(0) = 2.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Guarde o termo atual e o próximo em duas variáveis.
Dica 2
A única diferença em relação a Fibonacci é o começo: 2 e 1.
Dica 3
Para n = 90, o termo seguinte não caberia em 64 bits, então pare o laço em n.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.