归纳算法

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