N-ésimo número de Tribonacci
La misión
Problema
La secuencia de Tribonacci empieza con T(0) = 0, T(1) = 1 y T(2) = 1, y cada término siguiente es la suma de los tres anteriores: T(n) = T(n - 1) + T(n - 2) + T(n - 3). Dado n con 0 ≤ n ≤ 37, devuelve T(n).
Ejemplos
Input: n = 4
Output: 4
Por qué: la secuencia va 0, 1, 1, 2, 4
Input: n = 25
Output: 1389537
Input: n = 0
Output: 0
Por qué: caso límite: el primer valor inicial
Pistas
0 / 3
La definición ya es una función recursiva. Dibuja su árbol de llamadas para n = 6 y cuenta cuántas veces se calcula T(3).
Cada llamada se ramifica en tres, así que la recursión simple hace unas 1.84 elevado a n llamadas. Cada valor solo depende de los tres valores justo anteriores.
Guarda los últimos tres términos en tres variables y deslízalos hacia adelante n veces: la nueva terna es el segundo de antes, el tercero de antes y la suma de los tres.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- 0 ≤ n ≤ 37
Solución
La definición recursiva es correcta, pero recalcula los mismos términos una y otra vez, igual que el Fibonacci ingenuo de la lección, solo que peor, ya que cada llamada genera tres más en lugar de dos. La memoización lo arreglaría, pero la dependencia es tan corta que no hay nada que guardar en caché más allá de tres números. El bucle mantiene T(i), T(i + 1) y T(i + 2) y desplaza la ventana un paso por iteración, así que después de n pasos la primera posición contiene T(n). El tiempo es O(n) y el espacio es O(1), y con n hasta 37 la respuesta cabe en un entero 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)) # -> 0¿Lo que te frena es la idea y no el código? Factorial y Fibonacci lo explica.