N-ésimo número de Tribonacci
A missão
Problema
A sequência de Tribonacci começa com T(0) = 0, T(1) = 1 e T(2) = 1, e cada termo seguinte é a soma dos três anteriores: T(n) = T(n - 1) + T(n - 2) + T(n - 3). Dado n com 0 ≤ n ≤ 37, retorne T(n).
Exemplos
Input: n = 4
Output: 4
Por quê: a sequência segue 0, 1, 1, 2, 4
Input: n = 25
Output: 1389537
Input: n = 0
Output: 0
Por quê: edge case: é o primeiro valor inicial
Dicas
0 / 3
A definição já é uma função recursiva. Desenhe a árvore de chamadas para n = 6 e conte quantas vezes T(3) é calculado.
Cada chamada se ramifica em três, então a recursão pura faz cerca de 1,84 elevado a n chamadas. Cada valor só depende dos três valores imediatamente anteriores.
Guarde os três últimos termos em três variáveis e deslize-os para a frente n vezes: o novo trio é o antigo segundo, o antigo terceiro e a soma dos três.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- 0 ≤ n ≤ 37
Solução
A definição recursiva está correta, mas recalcula os mesmos termos de novo e de novo, exatamente como o Fibonacci ingênuo da aula, só que pior, já que cada chamada gera mais três em vez de duas. A memoização resolveria isso, mas a dependência é tão curta que não há nada para armazenar em cache além de três números. O loop mantém T(i), T(i + 1) e T(i + 2) e desloca a janela um passo por iteração; assim, depois de n passos, a primeira posição guarda T(n). O tempo é O(n) e o espaço é O(1), e n até 37 mantém a resposta dentro de um inteiro de 32 bits.
def tribonacci(n):
a, b, c = 0, 1, 1 # T(0), T(1), T(2)
for _ in range(n):
a, b, c = b, c, a + b + c # slide the window one term forward
return a
print(tribonacci(4)) # -> 4
print(tribonacci(25)) # -> 1389537
print(tribonacci(0)) # -> 0Travou na ideia, e não no código? Fatorial e Fibonacci explica isso.