Problem 326 Extrapolation Using a Difference Table，用差分表算外差

這題的差分表並不是真的要你宣告一個很大的陣列來儲存差分表，根據他最後的提示，似乎會給你一個很大的 k 值，如果你將每個值都存起來，可能就會有記憶體消耗的問題。
我的作法是先將每一行的最後一個值算出來，存在一個全域變數的陣列中，並使用遞迴呼叫來做解算。因為題目說最多只有10個值，所以遞迴所用的陣列大小10個就夠用。在下面的例子中，lastValue和m_index都是全域變數，每呼叫一次，就計算一行的差分值，然後只要將最後的一個值存起來，放入lastValue中就OK了。

void compDiff(int eArray[], int size)
{
    int ary[10]={0}, i;
    if (size==2)
    {
        m_index++;
        lastValue[m_index] = eArray[1]-eArray[0];
    }
    else
    {
        for (i=1;i<size;i++)
            ary[i-1] = eArray[i]-eArray[i-1];
        m_index++;
        lastValue[m_index] = ary[i-2];
        compDiff(ary,size-1);
    }
}

每一行最後的值算完後，再重複k次，每次再更新lastValue的每個值，使用
lastValue[j] += lastValue[j+1];
這樣就大功告成了。
p326題目連結
回ACM題庫目錄
回首頁