基于递归缓存的斐波那契

Question

我正在尝试实现基于缓存的斐波那契数列。但是它给了我错误的输出，例如（fibcache(8) 给了我 13 而不是 21 的答案。但是在某些情况下它给了我正确的输出。例如 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(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);
    }
}

基于递归缓存的斐波那契

Recursive Caching Based Fibonacci

c

algorithm

caching

fibonacci