15

Estoy haciendo esta funcion "Pentabonaci" que es casi lo mismo que la de fibonaci pero en vez de llamar n=f(n-1)+f(n-2) hace lo mismo hasta 5...(n=f(n-1)+f(n-2)+...+ f(n-5)) luego cuenta la cantidad de numeros impares en la secuencia y regresa este valor.. La funcion funciona.. el problema es que es muy lenta... para ~45 de la secuencia la consola se me bloquea... y mi funcion debe funcionar para numeros bastante grandes...

Nota: El objetivo de la funcion no es calcular los numeros de la secuencia es la cantidad de numeros impares de la secuencia...

function countOddPentaFib(n) {
    let arr = []
    for (let i = 1; i <= n; i++) {
        arr.push(calcPentaFib(i))
    }
    return arr.filter(n => n % 2)
}
function calcPentaFib(n) {
    if (n == 0) return 0;
    else if (n == 1 || n == 2) return 1;
    else if (n == 3) return 2;
    else if (n == 4) return 4;
    else {
        return calcPentaFib(n - 1) + calcPentaFib(n - 2) + calcPentaFib(n - 3) + calcPentaFib(n - 4) + calcPentaFib(n - 5)
    }
}

console.log(countOddPentaFib(30));

3
  • 1
    Utiliza "Memoization" para mejorar el rendimiento, si desconoces ese término, te invito a investigar :D
    – fredyfx
    el 21 oct. 2019 a las 23:35
  • 2
    Usas recursividad, y lamentablemente el motor de JS no permite optimización de cola (aún). Otra forma es usar lo que te sugieren: memoization, aunque no sé cómo aplica para tu caso, ya que tendrías que definir una estructura para almacenar los valores precalculados o repetitivos. Seguro que se puede optimizar de otra forma. Saludos el 22 oct. 2019 a las 7:12
  • 1
    Muy relacionada: es.stackoverflow.com/questions/190831/… el 22 oct. 2019 a las 12:37

3 respuestas 3

26

Vamos a usar Memoization para implementar una solución. Esto va a requerir crear una estructura para almacenar los datos pre calculados y así optimizar el tiempo de respuesta.

RECURSIÓN: "para entender la recursión primero debes entender la recursión".

Una de las características de la recursividad (o recursión) es que te permite escribir un código limpio y además permite ejecutar tareas complejas que de hacerlas de otra forma se volverían bastante tediosas.

Sin embargo, la recursión puede llegar a tener un coste muy alto en recursos si el problema crece en complejidad y no se toman medidas para optimizar el proceso.

JavaScript (ECMAScript 6) da soporte a la optimización de cola para la recursividad, sin embargo, no todos los motores (casi ninguno) de JS de los diferentes navegadores (incluyendo NodeJS), dan soporte a dicha característica.

Por lo tanto, debemos dejar el uso de la recursividad optimizada a lenguajes que si den soporte a la misma. (Al menos por ahora 22-10-2019).

Puedes leer un poco más sobre ES6 y la optimización de cola para recursividad, en este post.

MEMOIZATION, o era memorización ... no recuerdo

La técnica de memoization (no confundir con memorization) es una técnica de optimización usada para acelerar los procesos cuando se tienen llamadas a funciones muy pesadas. Existen diversos ámbitos en los que la misma es usada, no solo en recursividad.

Para resolver el problema usaremos esta técnica ya que parece la adecuada, aunque pudiese existir otra aún más eficiente.

Lo que haremos es crear una caché de resultados almacenados en una lista. De esta forma no necesitamos usar recursión, y el proceso se hace muy intuitivo.

La definición del problema pide calcular una serie llamada Penta-Fibonacci, es decir, aplicando la serie de Fibonacci pero hasta n-5.

Recordemos que el valor de cada elemento de la serie de Fibonacci se calcula de la siguiente manera:

n = (n -1) + (n - 2);

por lo tanto nuestra serie Penta-Fibonacci se define como:

n =  (n-1) + (n -2) + ... + (n -5);

La serie de fibonacci empieza con los valores 0 y 1 y el resto se calcula a partir de estos dos números. Siendo:

f(0) = 0;
f(1) = 1;
f(2) = 1;
f(3) = 2;
f(4) = 4;
...

Con esto ya tenemos los valores que servirán de base para calcular el resto de nuestra serie Penta-Fibonacci.

Necesitamos trabajar con una fila o cola, para ir almacenando siempre los últimos 5 elementos de la serie para calcular el siguiente. Javascript no tiene un objeto de tipo fila, sino que tiene un objeto de tipo Array, el cual posee dos métodos que nos ayudarán a trabajar como si fuese una fila. Estos son push(), que nos permite agregar elementos al final del array, y shift() que nos permite remover el primer elemento de array y reduce el array de tamaño.

El código, por favor

Vamos a implementar esta solución sin usar recursividad, simplemente usaremos un bucle for.

const pentaFiboOdd = function(n) {
  // Función que retorna los elementos impares de la serie Penta Fibonacci

  // Creamos el caché inicial de valores
  let cachedValues = [0, 1, 1, 2, 4];

  // Casos base:
  if(n < 0) return 0;
  if(n < 5) return cachedValues[n];

  // Creamos el array de resultados (sólo elementos impares)
  let result = cachedValues.filter(value => value % 2 !== 0);

  // función reductora para calcular la suma de los elementos en caché.
  const reducer = (acc, curr) => acc + curr;

  // iteramos desde i = 5 hasta n y calculamos los valores de cada elemento
  // que tiene la serie, basados en la suma de los 5 anteriores
  for(let i = 5; i <= n; i++){
    let elemento = cachedValues.reduce(reducer);
    // sólo si el elemento es impar lo añadimos al resultado
    if(elemento % 2 !== 0) {
      result.push(elemento);
    }
    // aunque el elemento no sea parte del resultado, debemos actualizar la caché
    cachedValues.push(elemento);
    cachedValues.shift();
  }
  return result;
}

let serie = pentaFiboOdd(50);
console.log('El resultado de pentaFiboOdd(50) es:');
console.log(serie);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Analicemos bien lo que pasa aquí.

  1. El caso base ya está cubierto y explicado.
  2. Hemos creado una lista llamada cachedValues, la misma contiene los primeros cinco elementos de nuestra serie.
  3. Cada nuevo elemento de la serie se calcula sumando los valores de los 5 elementos almacenados en nuestro caché.
  4. Si el resultado es impar se almacena en el array de resultado.
  5. Se purga el primer elemento de la caché y se agrega el nuevo elemento calculado a la caché. De esta forma garantizamos que siempre tendremos los últimos 5 elementos con los que se calcula el siguiente.

Con esto has aplicado Memoization, en un algoritmo no recursivo.

EDICIÓN

Dado que en el ejercicio (kata) de CodeWars del que proviene esta pregunta, se pide el número de impares que existen en la serie, entonces se podría usar otra lógica para hallar el resultado.

Gracias al aporte de @gbianchi, la idea por él planteada es usar un método determinístico para saber si dado un valor n el resultado de f(n) será par o impar.

Si analizamos los primeros 17 elementos de la serie tenemos lo siguiente.

f(0) = 0     // par
f(1) = 1     // impar
f(2) = 1     // impar
f(3) = 2     // par
f(4) = 4     // par
f(5) = 8     // par
f(6) = 16    // par
f(7) = 31    // impar
f(8) = 61    // impar
f(9) = 120   // par
f(10) = 236  // par
f(11) = 464  // par
f(12) = 912  // par
f(13) = 1793 // impar
f(14) = 3525 // impar
f(16) = 6930 // par
...

Vemos un patrón que se repite cada 6 elementos empezando con n=1. Por lo tanto la forma de contar dichos elementos impares viene dada por medio del cálculo de las veces que 6 cabe en n y el resto de dividir n / 6.

Por cada vez que 6 cabe enteramente en n se deben añadir 2 impares a la cuenta.

Y si la división de n/6 es inexacta, se debe agregar un impar a la cuenta de acuerdo a lo siguiente:

si n%6 > 2 se añaden 2 impares, en caso contrario se añade exactamente n%6 impares.

Por último hay que tener en cuenta que el valor 1 está repetido y por lo tanto debemos eliminarlo de la cuenta.

Veamos la solución:

const countPentaFiboOdd = function(n) {
  
  let count = Math.floor(n/6) * 2;
  const rest = n%6;
  if(rest < 3) {
    count += rest;
  } else {
    count += 2;
  }
  // dado que el 1 se repite cuando n  > 1, lo sacamos de la ecuación
  if (n > 1) count--;
  return count;
}

console.log(countPentaFiboOdd(1000));

Espero que esto te ayude a resolver el problema.

1
  • Genial Mauricio Gracias de nuevo
    – RazerJs
    el 22 oct. 2019 a las 20:47
9

Para calcular el valor para n = 7 tienes que calcular el valor de los 5 anteriores, con lo que haces 5 llamadas recursivas, pero cada una de estas llamadas hará otras 5, con lo que para el valor de n=30 tendrás una cantidad increíble de llamadas recursivas que acabarán con la pila. Muchas de estas llamadas se habrán hecho anteriormente, con lo que lo ideal sería reaprovecharlas.

Una solución sencilla es usar una estructura que guarde los resultados previos para evitar que la recursividad se te vaya de las manos:

Una vez que calculas PentaFib de N, lo guardas. Como habrás tenido que calcular PentaFb(N-1), PentaFb(N-2), ... PentaFb(N-5), tendrás todos esos valores ya guardados, con lo que calcular PentaFib(N+1) es acceder a los 5 valores ya guardados previos y sumarlos. Esto es lo que se llama memoización

Como sólo necesitas saber la cantidad de elementos impares hay, podemos simplificar aún más el cálculo:

Guardaremos 0 si es número es par y 1 si es impar. De ese modo tenemos que los valores iniciales:

[0, 1, 1, 2, 4]

pasan a ser

[0, 1, 1, 0, 0]

Y cada vez que calculemos el siguiente valor tendremos lo siguiente:

[0, 1, 1, 2, 4] -> f(5) = 8

Y con nuestra nueva función f prima:

[0, 1, 1, 0, 0] -> f'(5) = (0 + 1 + 1 + 0 + 0) mod 2 = 0

Con lo que al final sólo tendremos que contar el número de 1 en el array:

const pentafib = {
  results: [0, 1, 1, 0, 0], //resultados para n < 5
  calcPentaFib : function calcPentaFib(n) {
    
    if (this.results.length > n) { // está ya calculado
      return this.results[n];
      
    } else {
      const value = (this.calcPentaFib(n - 1) +
          this.calcPentaFib(n - 2) +
          this.calcPentaFib(n - 3) +
          this.calcPentaFib(n - 4) +
          this.calcPentaFib(n - 5)) % 2;
          
      //se guarda el resultado para posteriores peticiones
      this.results[n] = value;
      return value;
    }
  }
}

function countOddPentaFib(n) {
    let arr = []
    for (let i = 0; i <= n; i++) {
        arr.push(pentafib.calcPentaFib(i))
    }
    arr = arr.filter(n => n === 1); //nos quedamos con los 1
    //devolvemos el número de 1 encontrados
    return arr.length - 1; // restamos uno porque f(1) y f(2) son 1, con lo que tenemos un valor repetido
}

console.log(countOddPentaFib(30));
console.log(countOddPentaFib(100));

2
  • vale Pablo muchas gracias... eso hare, ayer estaba intentando hacer algo parecido pero ya para n=30 era un numero realmente grande pienso que con el crecimiento exponencial del numero para n=100 estare trabajando con numeros realmente grandes y tendre problemas por eso con la solucion
    – RazerJs
    el 22 oct. 2019 a las 9:53
  • Para números mayores de 100 tendrás el problema de que no cabrán en el formato estándar, tendrás que trabajar con BigInt o perderás precisión, pero mi solución tarda un par de segundos en obtener el valor para 100 el 22 oct. 2019 a las 9:57
8

La solucion de Mauricio es totalmente correcta.

Basado en la determinacion de datos y el patron recurrente, se puede hacer lo siguiente:

El codigo esta en c#, pero es traducible a cual lenguaje...

Mauricio uso una funcion matematica, todavia mas bonita. Sin embargo, usando solo codigo "trivial" se puede resolver tambien.

public static long CountOddPentaFib(long n) {
    int valor = 1;
    int inferior = 8;
    int suma = 1;
    if (n < inferior)
    {
        return valor;
    }
    while (inferior <= n+1)
    {
        valor++;
        inferior += suma;
        if (suma == 1)
        {
            suma = 5;
        }
        else
        {
            suma = 1;
        }
    }
    return valor;
}

Hay un tema si el valor de entrada es par o impar, y por eso el while toma un valor mas de los que hay que contar. No logre encontrar donde esta el problema en esos bordes, pero creo que aplica la solución de Mauricio.

3
  • 1
    En realidad el problema es que el kata pide el número de resultados impares diferentes, y el 1 se repite (0,1,1,2,4...), con lo que hay que restar 1 si el N es mayor que 2 el 22 oct. 2019 a las 14:21
  • 1
    @PabloLozano esta solucion ya excluye el repetido.. el problema esta cuando el valor de n es par.. no llegue a entender porque cuenta uno menos en esos casos...
    – gbianchi
    el 22 oct. 2019 a las 14:23
  • Claro! esto es una función con memoria. el 16 dic. 2019 a las 17:19

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.