Problema
Os números de tribonacci estendem a ideia de Fibonacci para três termos: T(0) = 0, T(1) = 0, T(2) = 1 e, a partir daí, T(n) = T(n − 1) + T(n − 2) + T(n − 3). A sequência fica 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …
Implemente tribonacci(n).
Entrada
n: o índice do termo, começando em 0.
Saída
Retorne T(n). A cada momento só os três últimos termos são necessários, então um laço com três variáveis basta.
Restrições
0 ≤ n ≤ 74
Exemplos
Entrada:
n = 7
Saída esperada:
expected = 13
Entrada:
long long n = 7;
Saída esperada:
long long expected = 13;
Entrada:
long n = 7;
Saída esperada:
long expected = 13;
Explicação
Os termos são 0, 0, 1, 1, 2, 4, 7, 13, então T(7) = 13.
Entrada:
n = 2
Saída esperada:
expected = 1
Entrada:
long long n = 2;
Saída esperada:
long long expected = 1;
Entrada:
long n = 2;
Saída esperada:
long expected = 1;
Explicação
T(2) é o primeiro 1 da sequência: 1.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Retorne os três primeiros termos diretamente.
Dica 2
Use três variáveis e desloque os valores entre elas a cada passo.
Dica 3
Uma solução recursiva sem memória repete trabalho e é lenta demais.
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.