为什么这个memoized函数返回错误的答案！

我已经memoized在C因子的功能如下：为什么这个memoized函数返回错误的答案！

int fact(int n) 
{ 
int temp; 
int lookup_table[n]; 
if(lookup_table[n]) 
    return lookup_table[n]; 
else{ 
    if(n == 0 || n == 1) 
     return 1; 
    else 
     temp = n * fact(n-1); 
     lookup_table[n] = temp; 
     return temp; 
    } 
}

但后来wehn我输入n = 5，它。OUPUTS
-1！ = 134514064
有人可以解释发生了什么？

来源

2011-04-24 station

int lookup_table[n]应该标记为静态（实际上它不能，你需要一个常量，但它不必太大，因为阶乘增长非常快），但它不是真的为什么你得到一个错误的答案。相反，lookup_table被初始化为不确定垃圾，而不是0。

但是，当你将它设置为静态时，它们没有理由将它初始化为零;这将自动完成。

哦，正如其他人指出的那样，您有一个越界误差，因为您需要交换int lookup_table[n]以使用常数而不是n。

来源

2011-04-24 12:25:41 alternative

您的lookup_table数组在本地声明;每次调用都有所不同;没有任何东西正在被记忆。

来源

2011-04-24 12:21:58

+1，他应该将其标记为静态。但是，这不是它得到错误答案的原因。（他还需要使用常数而不是'n'） – alternative 2011-04-24 12:23:21

int lookup_table[n];这个int lookup_table[n];声明了一个名为lookup_table的n个数组的数组。由于该数组的有效索引为0..n-1，因此lookup_table [n]不在数组中，并且会导致未定义的行为。我想，你想写：int somevariable = lookup_table[n];并使用此变量进行比较，或根本删除此行。

在任何情况下，请确保在访问该阵列时检查边界。

来源

2011-04-24 12:23:38 MByD

好吧，马上如果（lookup_table [n]）要超出lookup_table []长度的一个元素。在C中，数组具有基于0的索引。

然后存在一个问题，即您在查找表中将自动（堆栈）变量声明为应该填充它的递归函数。它需要在全局/模块范围内的函数外声明。

来源

2011-04-24 12:30:25 Christo

更换

int lookup_table[n];

与

static int lookup_table[13];

这将使同一阵列中的递归函数调用访问，给你足够的空间来存储所有的阶乘值的int范围可以支持。

这将是一个好主意，检查输入值是12或更少，以便您不会遇到未定义的行为。

来源

2011-04-24 12:35:51 AbdullahC

另外，在运行基本情况时，将fac [0]和fac [1]存储在查找表中。 – hugomg 2011-04-24 13:20:37

为什么这个memoized函数返回错误的答案！

回答

相关问题