爲什麼這個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函數返回錯誤的答案！

回答

相關問題