Рекурсивное кэширование на основе Fibonacci

Question

Я пытаюсь реализовать последовательность Фибоначчи на основе кеширования. Но это дало мне неправильный результат, например (fibcache (8) дал мне ответ 13 вместо 21. Однако в некоторых случаях он дал мне правильный результат. Например, фиккач (6) дал мне 8. Не могу понять, что случилось

#include <stdio.h> 
#include <stdlib.h> 
#define DCACHE_SIZE 5 

int fibcache(int number); 
long cacheodd[DCACHE_SIZE] = {0}; 
long cacheeven[DCACHE_SIZE] = {0}; 
int i_odd, i_even; 

int main(int argc, char *argv[]) 
{ 

    int fibNum = fibcache(6); 

    printf("The Fibonacci number is %d\n", fibcache(fibNum)); 

} 

int fibcache(int n) 
{ 
    int result; 

    if (n == 0) 
     return 0; 
    if (n == 1) 
    return 1; 

    if(n%2==0) 
    { 
     if (cacheodd[i_odd] != 0) 
      result = cacheodd[i_odd]; 
     else 
     { 
      cacheodd[i_odd] = fibcache(n-1) + fibcache(n-2); 
      result = cacheodd[i_odd]; 
     } 
    } 
    else 
    if(n%2==1) 
    { 
     if (cacheeven[i_even] != 0) 
      result = cacheeven[i_even]; 
     else 
     { 
      cacheeven[i_even] = fibcache(n-1) + fibcache(n-2); 
      result = cacheeven[i_even]; 
     } 
    } 
    return result; 
} 

Answer 1

у вас есть какие-то проблемы:.

• Вы на самом деле печатать fib(fib(6)), гораздо большее число, чем fib(6)

• Ваша функция кэширования слишком сложна: почему обрабатывать четные и нечетные числа по-разному ? Вы должны сделать особый случай чисел больше размера кеша и проверить, было ли вычислено кэшированное значение.

Вот упрощенная версия:

#include <stdio.h> 

#define DCACHE_SIZE 5 

long fibcache(int number); 
long fibcache_values[DCACHE_SIZE] = { 0 }; 

int main(void) { 
    printf("List of Fibonacci numbers:\n"); 
    for (int i = 0; i < 47; i++) { 
     printf(" fib(%d) = %ld\n", fibcache(i)); 
    } 
    return 0; 
} 

long fibcache(int n) { 
    if (n <= 0) 
     return 0; 
    if (n == 1) 
     return 1; 
    if (n < DCACHE_SIZE) { 
     if (fibcache_values[n] != 0) 
      return fibcache_values[n]; 
     else 
      return fibcache_values[n] = fibcache(n - 1) + fibcache(n - 2); 
    } else { 
     return fibcache(n - 1) + fibcache(n - 2); 
    } 
}