#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#define N 20
void Difference(float *x,float *y,int n)
{
	float *f;
	int i,j;
	f=new float[n];
	for(i=1;i<=n;i++)
	{
		f[0]=y[i];
		for(j=0;j<i;j++)
			f[j+1]=(f[j]-y[j])/(x[i]-x[j]);
		y[i]=f[i];
	}
	return;
}
void main()
{
	int i,n;
	float x,y;
	float a[N];
	float b[N];

	cout<<"請輸入插值多項式的次數:"<<endl;
	cin>>n;
	cout<<"請輸入數據x:"<<endl;
	for(i=0;i<=n;i++)
		cin>>a[i];
	cout<<"請輸入數據y:"<<endl;
	for(i=0;i<=n;i++)
		cin>>b[i];
	cout<<"請輸入所求x:"<<endl;
	cin>>x;
	Difference(a,(float *)b,n);
	y=b[n];
	for(i=n-1;i>=0;i--)
		y=y*(x-a[i])+b[i];
	cout<<"最后的運算結果是:"<<"x="<<x<<"   "<<"y="<<y<<endl;
}