首页 / 算法 / 算法分析中递推式的一般代数解法 张洋

算法分析中递推式的一般代数解法 张洋

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法分析中递推式的一般代数解法 张洋，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1459字，纯文字阅读大概需要3分钟。

内容图文

http://blog.codinglabs.org/articles/linear-algebra-for-recursion.html

另介绍一种算法

Berlekamp-Massey算法，常简称为BM算法，是用来求解一个数列的最短线性递推式的算法。

#include <bits/stdc++.h>
usingnamespace std;
typedef longlong ll;
constdouble eps = 1e-7;
constint maxn = 1e5 + 5;
vector<double> ps[maxn];
int fail[maxn];
double x[maxn], delta[maxn];
int n;
int pn;
/*
前提：必须符合线性递推，如：
fib: 1 1 2 3 5 8 13 21 34 55 89
*/int main()
{
    while (~scanf("%d", &n)) // n 项    {
        pn = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lf", &x[i]); //前 n项        }
        for (int i = 1; i <= n; i++)
        {
            double dt = -x[i];
            for (int j = 0; j < (int)ps[pn].size(); j++)
            {
                dt += x[i - j - 1] * ps[pn][j];
            }
            delta[i] = dt;
            if (fabs(dt) <= eps) continue;
            fail[pn] = i;
            if(!pn)
            {
                ps[++pn].resize(1);
                continue;
            }
            vector<double>&ls = ps[pn - 1];
            double k = -dt / delta[fail[pn - 1]];
            vector<double> cur;
            cur.resize(i - fail[pn - 1] - 1);
            cur.push_back(-k);
            for(int j = 0; j < (int)ls.size(); j++)
            {
                cur.push_back(ls[j] * k);
            }
            if((int)cur.size() < (int)ps[pn].size())
            {
                cur.resize(ps[pn].size());
            }
            for(int j = 0; j < (int)ps[pn].size(); j++)
            {
                cur[j] += ps[pn][j];
            }
            ps[++pn] = cur;
        }
        int len = (int)ps[pn].size();
        std::cout << "f[i]=" ;
        for (int i = 0; i < len; i++)
        {
            if(ps[pn][i] > 0 && i > 0)std::cout << "+";
            if(ps[pn][i]==0)continue;
            printf("%g*f[i-%d]", ps[pn][i], i+1);
        }
    }
    return0;
}

 

原文：https://www.cnblogs.com/polya/p/9711038.html

内容总结

以上是互联网集市为您收集整理的算法分析中递推式的一般代数解法 张洋全部内容，希望文章能够帮你解决算法分析中递推式的一般代数解法 张洋所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1233701.html

来源：【匿名】