#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
	int a,b;
	double z,r1,r2,r3;
	
	cout<<"請輸入X節(jié)點數(shù)：";
	cin>>b;
	cout<<endl;
	double x[10],f[10];
	cout<<"輸入x:";
	for(a=0;a<b;a++)
	{
		cin>>x[a];
	}
	cout<<endl<<"輸入對應(yīng)的f(x):";
	for(a=0;a<b;a++)
	{
		cin>>f[a];
	}
	cout<<endl;
	cout<<"x"<<setiosflags(ios::right);
	for(a=0;a<b;a++)
	{
		cout<<setw(12)<<x[a];
	}
	cout<<endl<<"f(x)";
	for(a=0;a<b;a++)
	{
		cout<<setw(12)<<f[a];
	}
	cout<<endl;
	while(1)
	{
		cout<<"請輸入計算點X值：";
		cin>>z;
		cout<<endl;
	
		if(z>x[0]&&z<x[b-1])
		{	double lg1(double *a,double *b,int n,double z);
			double lg2(double *a,double *b,double z);
			double lg3(double *a,double *b,int n,double z);
			r1=lg1(x,f,b,z);
			r2=lg2(x,f,z);
			r3=lg3(x,f,b,z);
			cout<<"分段線性插值："<<r1<<endl;
			cout<<"分段二次插值："<<r2<<endl;
			cout<<"全區(qū)間上的拉格朗日插值："<<r3<<endl;
			cout<<endl;
		}
		else
			cout<<"超出范圍，輸入的計算點無效。"<<endl;
         cout<<endl;
	}
	return 0;
}
double lg1(double *a,double *b,int n,double z)
{
	int i;
	double r;
	for(i=1;i<=n;i++)
	{
		if(z>a[i-1]&&z<a[i])
		r=b[i-1]*(z-a[i])/(a[i-1]-a[i])+b[i]*(z-a[i-1])/(a[i]-a[i-1]);

	}
	return r;
}

double lg2(double *a,double *b,double x)
{
	double p=0;
  for(int i=0;i<10;i++)
  if(x>=a[i]&&x<a[i+1])
  if(i+2<10)
     

p=b[i]*((x-a[i+1])*(x-a[i+2]))/((a[i]-a[i+1])*(a[i]-a[i+2]))+b[i+1]*((

x-a[i])*(x-a[i+2]))/((a[i+1]-a[i])*(a[i+1]-a[i+2]))+b[i+2]*((x-a[i])*(

x-a[i+1]))/((a[i+2]-a[i])*(a[i+2]-a[i+1]));
  else
     

p=b[i-1]*((x-a[i])*(x-a[i+1]))/((a[i-1]-a[i])*(a[i-1]-a[i+1]))+b[i]*((

x-a[i-1])*(x-a[i+1]))/((a[i]-a[i-1])*(a[i]-a[i+1]))+b[i+1]*((x-a[i-1])

*(x-a[i]))/((a[i+1]-a[i-1])*(a[i+1]-a[i]));
 return p;
		
	
}

double lg3(double *a,double *b,int n,double z)
{
	double r=0;
	for(int k=0;k<n-1;k++)
	{
		double y=1.0;
		for(int j=0;j<n-1;j++)
		{
			if(j!=k)
			y=y*(z-a[j])/(a[k]-a[j]);
		}
		r=r+y*b[k];
	}
	return r;
}