Advertisement
Miquel_Fuster

Fibonacci con memoización

Jan 19th, 2022
857
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <stdint.h>
  5. #include <string.h>
  6.  
  7. // Lleva el registro de los números de fibonacci. Está realizada a modo de singleton.
  8. struct {
  9.     // El máximo número de la lista que se ha calculado
  10.     unsigned max_num;
  11.     // Marca las posiciones que se han calculado
  12.     bool *calculado;
  13.     // Tiene los max_num primeros números de fibonacci calculados
  14.     uint64_t *data;
  15. } cache;
  16.  
  17. // Inicializa la estructura cache
  18. void inicializar() {
  19.     cache.max_num = 1;
  20.  
  21.     // Sólo ofrecerá, desde un inicio, los casos bases del 0 y el 1
  22.     cache.calculado = malloc(2 * sizeof(bool));
  23.     cache.calculado[0] = cache.calculado[1] = true;
  24.  
  25.     cache.data = malloc((cache.max_num + 1) * sizeof(uint64_t));
  26.     cache.data[0] = 0;
  27.     cache.data[1] = 1;
  28. }
  29.  
  30. // Hace crecer la capacidad de la cache en caso de que el número a calcular
  31. // sea mayor que el mayor que hay en la estructura
  32. void actualizar(unsigned x) {
  33.     if(x > cache.max_num) {
  34.        
  35.         // Las nuevas posiciones que se crean deben estar a 0 (false)
  36.         void *aux = calloc((x + 1), sizeof(bool));
  37.         memcpy(aux, cache.calculado, (cache.max_num + 1) * sizeof(bool));
  38.         free(cache.calculado);
  39.         cache.calculado = aux;
  40.         cache.max_num = x;
  41.  
  42.         // Las nuevas posiciones pueden tener cualquier dato por lo que
  43.         // realloc es una opción más rápida que todo el código anterior
  44.         aux = realloc(cache.data, (x + 1) * sizeof(uint64_t));
  45.         cache.data = aux;
  46.  
  47.         cache.max_num = x;
  48.     }
  49. }
  50.  
  51. // Libera la memoria capturada para la caché
  52. void finalizar() {
  53.     free(cache.calculado);
  54.     free(cache.data);
  55. }
  56.  
  57. // Devuelve el número de fibonacci n-simo
  58. uint64_t fib(unsigned n) {
  59.     // Mirar si la cache debe crecer
  60.     actualizar(n);
  61.  
  62.     // Comprobar si el número ya fué calculado
  63.     if(!cache.calculado[n]) {
  64.         // En caso de no estarlo calcularlo y meterlo en la caché
  65.         cache.data[n] = fib(n-1) + fib(n-2);
  66.         cache.calculado[n] = true;
  67.     }
  68.  
  69.     // Devolver el número de fibonacci n-simo
  70.     return cache.data[n];
  71. }
  72.  
  73. int main() {
  74.     inicializar();
  75.  
  76.     // 93 es en mayor número n-simo capaz de ser calculado por
  77.     // por una máquina de 64 bits.
  78.     for(unsigned i=93; i > 0; --i) {
  79.         printf("fib(%u) = %I64u\n", i, fib(i));
  80.     }
  81.    
  82.     finalizar();
  83. }
  84.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement