//author  Duanjing
#include<iostream.h>
void main()
{   
	int n,i,j;
	float X[15];
	float D[15];
	float t,L;	
	char a;
	cout<<"輸入插值多項式的次數n=";
	cin>>n;
    cout<<"輸入節點Xi以及f(Xi):"<<endl;
	cout<<"節點個數在15個以內"<<endl;
	for(i=0;i<=n;i++)
	{  cout<<"X["<<i<<"]=";
	cin>>X[i];
	cout<<"f[X"<<i<<"]=";
	cin>>D[i];
	}
	i=1;
//計算均差
	for(;i<=n;i++)
	{
		if(i!=j)
		{
			for(j=n;j>=i;j--)
		{D[j]=(D[j]-D[j-1])/(X[j]-X[j-i]);}
		}
	   else                                                                           {continue;}
	}
	//計算插值
		do{
		cout<<"輸入插值點t:"<<endl;
		cin>>t;
		 float p;
		 p=D[n];
		 L=1;
		 for(i=n-1;i>=0;i--)
		 {
			 p=D[i]+(t-X[i])*p;}
		 cout<<"(t,p)="<<"("<<t<<","<<p<<")"<<endl;
		 cout<<"繼續計算嗎?   按y繼續,按其他任意鍵結束插值    ";
	     cin>>a;}while(a=='y');
         cout<<"牛頓插值結束!"<<endl;
}