BM算法【实数模板】
2023-09-27 14:27:45 时间
BM递推杜教版是在整数取模的情况下的,
这个可以求解实数系数,但是可能有精度误差。
若一个问题的结论是通过推线性递推式来解,考虑到实际的情况,可以用BM算法的模板,先输入项数再依次输入项,项越多越准确(按道理,前k项的递推,只需要2*k 个初始项就能确定)
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define mem(a,p) memset(a,p,sizeof(a)) #define MAXN 1005 struct BM { int n{}; vector<double> ps[MAXN]; int pn{},fail[MAXN]{}; double delta[MAXN]{}; void Solve(const double *x,int n) { pn=0; mem(fail,0); mem(delta,0); ps[0].clear(); rep(i,1,n+1) { double dt=-x[i]; rep(j,0,ps[pn].size()) dt+=x[i-j-1]*ps[pn][j]; delta[i]=dt; if(fabs(dt)<=1e-8)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); rep(j,0,ls.size())cur.push_back(ls[j]*k); if(cur.size()<ps[pn].size())cur.resize(ps[pn].size()); rep(j,0,ps[pn].size())cur[j]+=ps[pn][j]; ps[++pn]=cur; } } void print() { cout<<setiosflags(ios::fixed)<<setprecision(10); for(int i = 0;i<ps[pn].size();++i) { cout<<ps[pn][i]<<" "; } cout<<endl; } }B; double x[MAXN]; int main() { int n; while(cin>>n) { for(int i = 1;i<=n;++i) { cin>>x[i]; } B.Solve(x,n); B.print(); } }
Code From:
相关文章
- C++标准模板库STL算法与自适应容器(栈和队列)
- javascript 常用方法 解析URL,补充前导字符, 省市联动, 循环替换模板
- 【工程应用六】 继续聊一聊高效率的模板匹配算法(分水岭助威+蒙版提速)。
- 【工程应用五】 opencv中linemod模板匹配算法诸多疑惑和自我解读。
- 前端模板的原理与实现
- Pyhton编程:Django模板中引用css文件
- Django模板操作
- springboot 使用FreeMarker模板(转)
- 基于模板的图像拼接
- 设计模式系列1 - 模板模式&策略模式
- HDU 2255 奔小康赚大钱 (KM算法 模板题)
- 干货分享!12款响应式的移动网站模板免费下载
- Metronic – 超赞!基于 Bootstrap 的响应式后台管理模板
- 使用Python和OpenCV进行多尺度模板匹配
- java模板和回调机制学习总结
- Egg.js 项目中怎么使用前端模板
- 【luogu P6178】【模板】Matrix-Tree 定理(行列式)(数学)(树)
- 【luogu P4718】【模板】Pollard-Rho算法(数学)(也含 Miller Rabin)
- 【luogu P3806】【模板】点分治1
- 【luogu P6466】分散层叠算法(Fractional Cascading)(二分)(模板)
- 3.设计模式-模板方法模式Template Method