Fácil 0 resolvidos 0% de aceitação

Lucas Numbers

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

O que você vai aprender

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

Problema

Ver tradução

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

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

The terms are 2, 1, 3, 4, 7, 11, 18, so 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

The sequence starts with L(0) = 2.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Keep the current and next terms in two variables.

Dica 2

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

Dica 3

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

Complexidade esperada

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

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.