// work2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"
#define MAX_N 20

struct point_type
{
	double x;
	double y;
}point[MAX_N+1];


int main(int argc, char* argv[])
{
	int n;
	int i,j;
	double cs[MAX_N+1];
	double x,temp,newton;
	
//輸入數(shù)據(jù)的個(gè)數(shù)
	cout<<"輸入點(diǎn)個(gè)數(shù)n(從零開始記數(shù)):";
	cin>>n;
//確認(rèn)輸入的數(shù)在正確輸入范圍
	while ((n>MAX_N)||(n<0))
	{
		cout<<"輸入點(diǎn)個(gè)數(shù)必須在范圍 1 到"<<MAX_N<<endl;
		cout<<"重新輸入n:";
	    cin>>n;
	}
//輸入數(shù)據(jù)
	
	cout<<"輸入x_i,y_i,i=0.."<<n<<": "<<endl;   
	for (i=0;i<=n;i++)
	{		 
		    cin >>point[i].x>>point[i].y;

	}
	cout<<"輸入要求的x : "<<endl;
	cin>>x;
//初始化cs[i]
	for (i=0;i<=n;i++)
	{
		cs[i]=point[i].y;
	}
//求出最高階差商
	for(i=0;i<n;i++)
	{
		for(j=n;j>i;j--)
		{
			cs[j]=(cs[j]-cs[j-1])/(point[j].x-point[j-1-i].x );
		}
	}

	temp=1;
	newton=cs[0];
    for (i=0;i<n;i++)
	{
		temp=temp*(x-point[i].x);
		newton=newton+temp*cs[i+1];
		
	}
	cout<<"newton("<<x<<")="<<newton;
	return 0;
}