Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Números de Lucas

Retorne o n-ésimo número de Lucas, a sequência parecida com a de Fibonacci que começa com 2, 1.

O que você vai aprender

  • Calcular uma sequência parecida com a de Fibonacci
  • Usar os valores iniciais corretos
  • Evitar calcular um termo além da resposta

Problema

Ver original (inglês)

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

Exemplo 1
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.

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.