学步园

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 100
double Langrange(double x[],double y[],int n,double xx)
{
	double ans=0;
	for(int i=0;i<=n;i++){
		double tmp=1;
		for(int j=0;j<=n;j++){
			if(i==j)continue;
			tmp*=(xx-x[j])/(x[i]-x[j]);
		}
		ans+=tmp*y[i];
	}
	return ans;
}
double Newton(double x[],double y[],int n,double xx)
{
	double ma[maxn][maxn];
	memset(ma,0,sizeof(ma));
	for(int i=0;i<=n;i++)ma[i][0]=y[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ma[i][j]=(ma[i][j-1]-ma[i-1][j-1])/(x[i]-x[i-j]);
	double ans=0,tmp=1;
	for(int i=0;i<=n;i++){
		ans+=tmp*ma[i][i];
		tmp*=(xx-x[i]);
	}
	return ans;
}
double x[maxn],y[maxn];
int main()
{
	int n;
	while(true){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<=n;i++)scanf("%lf",&x[i]);
		for(int i=0;i<=n;i++)scanf("%lf",&y[i]);
		double xx;
		scanf("%lf",&xx);
		double ans1=Langrange(x,y,n,xx);
		double ans2=Newton(x,y,n,xx);
		printf("%lf %lf\n",ans1,ans2);
	}
	return 0;
}

今天在马原课上写的。。。。。

代码里面的n代表的是x0,x1,x2,x3……xn的n

刚开始以为牛顿插值前提必须是x0,x1,x2……xn,按照一定的顺序排列，错了~

实测数据不多。估计会有错误。