データ予測（笑）

N個の（順序付き）データ a[0], a[1], ..., a[N-1] があったとして、N+1 番目のデータ a[N] を予測することを考えます。

注） 本気で予測するつもりは更々無いので、それ目的の人は、ここらでお引取りを……。

方法としては、

a[0] = f(0)
a[1] = f(1)
...
a[N-1] = f(N-1)

となる N-1次多項式 f(x) を求めて、f(N) を計算します。

具体的には、f(x)を、f(x) = b[N]・x^(N-1) + b[N-1]・x^(N-2) + ... + b[1]・x + b[0] と考え、
a[0] = f(0)
a[1] = f(1)
...
a[N-1] = f(N-1)
を代入して連立方程式を解いて b[0] ～ b[N] を求めます。

これをプログラムで解こうと思うと色々と面倒なのですが（行列計算ライブラリを利用すれば、それほどでもない）、a[N]の値を計算するだけなら、こんなプログラムで計算できます。

    double a[N] = {...};

    for (int j = N; j > 1; j--) {
        for (int i = 0; i < j - 1; i++) {
            a[i] = a[i + 1] - a[i];
        }
    }

    return std::accumulate(a, a + N, 0.0);

タグ：C++