///////////////////////////////////////////////
//     (x_i,y_i)的牛頓插值多項式             //
///////////////////////////////////////////////
#include "stdio.h"
#define MAX_N 20 //	定義(x_i,y_i)的最大維 (x_i,y_i)的牛頓插值多項式數
typedef struct tagPOINT//點的結構
{
	double x;
	double y;
}POINT;
int main()
{
	int n;
	int i,j;
	POINT points[MAX_N+1];double diff[MAX_N+1];
	double x, tmp,newton=0;
	printf("\nInput n value:");// 輸入被插值點的數目
	scanf("%d",&n);
	if(n>MAX_N)
	{
		printf("The input n is larger than MAX_N,please redefine the MAX_N.\n");
		return 1;
	}
	if(n<=0)
	{
		printf("Please input a number between 1 and %d.\n",MAX_N);
		return 1;
	}
	  //輸入配插值的點(x_i,y_j)
	printf("Now input the (x_i,y_j),i=0,...,%d:\n",n);
	for(i=0;i<=n;i++)
		scanf("%lf%lf",&points[i].x,&points[i].y);
	printf("INput the x value");//輸入計算牛頓插值多項式的x值
	scanf("%lf",&x);
	for(i=0;i<=n;i++)diff[i]=points[i].y;
	for(i=0;i<n;i++)
	{
		for(j=n;j>i;j--)
		{
			diff[j]=(diff[j]-diff[j-1])/(points[j].x-points[j-1-i].x);
		}//計算f(x_0,...,x_n)的差商
	}
	tmp=1;newton=diff[0];
	for(i=0;i<=n;i++)
	{
		tmp=tmp*(x-points[i].x);
		newton=newton+tmp*diff[i+1];
	}
	printf("newton(%f)=%lf\n",x,newton);
	return 0;

}