Fácil 0 resueltos 0% de aceptación

Tribonacci

Devuelve el n-ésimo número de tribonacci, en el que cada término es la suma de los tres anteriores.

Lo que aprenderás

  • Calcular una sucesión de forma iterativa
  • Guardar solo los últimos términos
  • Tratar directamente los términos iniciales

Problema

Ver original (inglés)

Los números de tribonacci llevan la idea de Fibonacci a tres términos: T(0) = 0, T(1) = 0, T(2) = 1 y, a partir de ahí, T(n) = T(n − 1) + T(n − 2) + T(n − 3). La sucesión es 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …

Implementa tribonacci(n).

Entrada

n: el índice del término, empezando en 0.

Salida

Devuelve T(n). En cada momento solo necesitas los tres últimos términos, así que basta con un bucle y tres variables.

Restricciones

0 ≤ n ≤ 74

Ejemplos

Ejemplo 1
Entrada:
n = 7

Salida esperada:
expected = 13
Entrada:
long long n = 7;

Salida esperada:
long long expected = 13;
Entrada:
long n = 7;

Salida esperada:
long expected = 13;

Explicación

Los términos son 0, 0, 1, 1, 2, 4, 7, 13, así que T(7) = 13.

Ejemplo 2
Entrada:
n = 2

Salida esperada:
expected = 1
Entrada:
long long n = 2;

Salida esperada:
long long expected = 1;
Entrada:
long n = 2;

Salida esperada:
long expected = 1;

Explicación

T(2) es el primer 1 de la sucesión: 1.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Devuelve directamente los tres primeros términos.

Pista 2

Usa tres variables y desplázalas en cada paso.

Pista 3

Una solución recursiva sin memoria repite trabajo y es demasiado lenta.

Complejidad esperada

tiempo O(n), espacio extra O(1)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.