用 double 类做拉格朗日插值,误差很大吗
查看原帖
用 double 类做拉格朗日插值,误差很大吗
483966
一粒夸克楼主2021/11/10 19:34

如题,拉差只能在模意义下做吗

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int dp[1<<18],lim[25][25];
namespace Lagrange{
	double a[3],f[3];
    inline double solve(int k){
     	double res=0;
	    for(int i=0;i<3;i++){
			double tmp=f[i];
			for(int j=0;j<3;j++){
				if(i!=j)tmp*=(a[j]-k)/(a[j]-a[i]);
			}res=res+tmp;
    	}//cout<<res<<endl;
		return res;
    }
}
using Lagrange::solve;
using Lagrange::a;
using Lagrange::f;
double x[25],y[25];
inline void init(int i,int j){
	if(i==j){lim[i][j]=(1<<i);return ;}
	lim[i][j]=0;
	a[1]=x[i];a[2]=x[j];f[1]=y[i];f[2]=y[j];
	for(int t=0;t<n;t++)if(fabs(solve(x[t])-y[t])<=1e-6)lim[i][j]|=(1<<t);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			scanf("%lf%lf",&x[i],&y[i]);
		}
		memset(dp,0x3f,sizeof(dp));dp[0]=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)init(i,j);//,cout<<i<<" "<<j<<" :"<<lim[i][j]<<endl;;
		}
		for(int s=0;s<(1<<n)-1;s++){
			int j=0;while((s>>j)&1)j++;
			for(int t=0;t<n;t++)dp[s|lim[j][t]]=min(dp[s|lim[j][t]],dp[s]+1);
		}printf("%d\n",dp[(1<<n)-1]);
	}

	return 0;
}

还是说我哪里写挂了

2021/11/10 19:34
加载中...