再帰キャッシュベースのフィボナッチ

Question

フィボナッチをベースにしたキャッシュを実装しようとしています。しかし、それは私に間違った出力を与えました（fibcache（8）は21の代わりに13の答えを与えました）。しかし、場合によっては正しい出力を得ました。例えばfibcache（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(6)よりもはるかに大きい数をfib(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); 
    } 
}