algorithm - 2 つの列の間の方程式を見つけるには

Question

入力としてテーブルがあります

A B 
3 20
5 30
6 35

2 つの列 A と B に関連付けられた式 (Equation) を見つけるアルゴリズムが必要です

出力

B=(A+1)*5

Answer 1

必要な式が多項式であると仮定します。

私たちが知っていることは？A値のリストについては、B値があります。「n」のA値を使用すると、見つけることができる最良の多項式は（n-1）次数です。なんで？

基本的に、私は次のような線形システムを解いています。

x + Ay + (A^2)z = B

例：

x + 3y + 9z = 20
x + 5y + 25z = 30
x + 6y + 35z = 35

これを解くと、（x、y、z）=（5、5、0）であることがわかります。これは、多項式が5 + 5A + 0（A ^ 2）であることを意味します。これは、基本的に、例で示したB =（A + 1）*5と同じです。

どのような方法でもシステムを解くことができます。それが役立つかどうかはわかりませんが、ガウスの消去法（Python）で解決するためにここにいくつかのコードを投げます：

def solve(A, B):
    n = len(A)
    M = [[a**i for i in range(n)]+[b] for a,b in zip(A,B)]

    for i in range(n):
        M[i] = [x / M[i][i] for x in M[i]]

        for j in range(n):
            if j==i: continue
            M[j] = [xj - xi * M[j][i] for xi, xj in zip(M[i], M[j])]

    return [M[i][-1] for i in range(n)]

print solve([3,5,6], [20, 30, 35])