歸納算法

Question

我有這樣的問題：

beta(1) = b(1); 
beta(2) = b(2) - a(1)*beta(1) 
beta(3) = b(3) - a(1)*beta(2) - a(2)*beta(1) 
beta(4) = b(4) - a(1)*beta(3) - a(2)*beta(2)- a(3)*beta(1) 
. 
. 
. 
beta(n) = b(n) - a(1)*beta(n-1)....a(n-2)*beta(2) - a(n-1)*beta(1) 

現在，當我有b即b(1)到b(4) 4個值，那麼我將永遠有a即a(1)到a(3) 3個價值觀和我算算beta(1)到beta(4)。所以要計算的beta的數量取決於值的數量b。

我不能硬編碼它，因爲有1000個要計算的值。我如何推廣它，即如何以編程方式獲得給定的b，a和任意n的所有值？

Answer 1

你可以用一個數組和聰明的變量來完成它。 代碼Java中（請注意，Java的開始索引0，而不是1）：

for (int i = 0; i < beta.length; i++) { 
    beta[i] = b[i]; 
    for (int j = 0; j < i; j++) { 
     beta[i] = beta[i] - a[j]*beta[i-j-1]; 
    } 
} 

，那麼你必須

beta[0] == b[0] 
beta[1] == b[1] - a[0]*beta[0] 
beta[2] == b[2] - a[0]*beta[1] - a[1]*beta[0] 

等

Answer 2

，這似乎是有效的給我一個解決辦法作爲一種向量，以b作爲某種形式的記憶遞歸。這裏是我的僞代碼實現

MEMO := ALLOCATE(LENGTH(B)) 
DEFINE BETA(N) 
    IF N = 1 
     RETURN B[1] 
    ELSE IF MEMO[N] != 0 
     RETURN MEMO[N] 
    ELSE 
     MEMO[N] := B[N] 

     FOR I IN 1 TO N - 1 
      MEMO[N] := MEMO[N] - A[I]*BETA[N-I] 
     END FOR 

     RETURN MEMO[N] 
    END IF 
END DEFINE