通过数据前几项找出递推关系（板子）

数论

#include<bits/stdc++.h>
using namespace std;
#define ld double
const int SZ=1e5;
int n;
typedef vector<ld> vld;
vld ps[2333];
int pn=0,fail[SZ];
ld x[SZ],delta[SZ];
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%lf",x+i);
    for(int i=1; i<=n; i++)
    {
        ld dt=-x[i];
        for(int j=0; j<ps[pn].size(); j++)
            dt+=x[i-j-1]*ps[pn][j];
        delta[i]=dt;
        if(fabs(dt)<=1e-7) continue;
        fail[pn]=i;
        if(!pn)
        {
            ps[++pn].resize(1);
            continue;
        }
        vld&ls=ps[pn-1];
        ld k=-dt/delta[fail[pn-1]];
        vld cur;
        cur.resize(i-fail[pn-1]-1); //trailing 0
        cur.push_back(-k);
        for(int j=0; j<ls.size(); j++) cur.push_back(ls[j]*k);
        if(cur.size()<ps[pn].size()) cur.resize(ps[pn].size());
        for(int j=0; j<ps[pn].size(); j++) cur[j]+=ps[pn][j];
        ps[++pn]=cur;
    }
    for(unsigned g=0; g<ps[pn].size(); g++)
        printf("%f ",ps[pn][g]);
    return 0;
}

用法举例

已知前$9$项为$1,5,11,36,95,281,781,2245,6336$
对于代码输入$9$,然后输入这就个数
跑出来的结果为$1.000000 , 5.000000 , 1.000000 , -1.000000$
表示当前项与前四项相关。
推出公式为$F[i] = F[i-1] + 5*F[i-2] + F[i-3] - F[i-4]$