#ifndef NEWTON_DEF_
#define NEWTON_DEF_
class CNewton
{
double *f[2];
double *x;
int max;
int n;
public:
CNewton(int MaxN);//MaxN 為最大插值點數 可任意設定
~CNewton();
void InsertPoint(double X,double Y);
double GetValue(double X);
};
#endif

// file: newton.cpp
#include "newton.h"
#include "assert.h"
#include "math.h"
#ifndef NULL
#define NULL 0
#endif
CNewton::CNewton(int MaxN)
{
max=MaxN+1;
n=0;
x=new double[max];
f[0]=new double[max];
f[1]=new double[max];
assert(x!=NULL);
assert(f[0]!=NULL);
assert(f[1]!=NULL);
}
CNewton::~CNewton()
{
if(x)
delete[]x;
if(f[0])
delete[]f[0];
if(f[1])
delete[]f[1];
}
void CNewton::InsertPoint(double X,double Y)
{
int i;
double fw;
assert(n<max);
//重復點檢查
for(i=0;i<n;++i)
if(fabs(X-x[i])<1e-5)
return;
//如果確保不會有重復點可刪去上面語句
x[n]=X;
fw=Y;
for(i=1;i<=n;++i)
{
double tmp=fw;
fw=(fw-f[1][i-1])/(x[n]-x[n-i]);
f[1][i-1]=tmp;
}
f[0][n]=f[1][n]=fw;
n++;
}
double CNewton::GetValue(double X)
{
if(n==0)
return 0.0;
double s=f[0][n-1];
for(int i=n-2;i>=0;--i)
{
s=s*(X-x[i])+f[0][i];
}
return s;
}

// file: test cpp
#include "newton.h"
#include "iostream.h"
int main(void)
{
int n;
double x,y;
CNewton nt(20);
cout<<"輸入插入點個數(n<=20)\nn=";
cin>>n;
for(int i=1;i<=n;++i)
{
cout<<"輸入第"<<i<<"個點\nx=";
cin>>x;
cout<<"y=";
cin>>y;
nt.InsertPoint(x,y);
}
while(1)
{
cout<<"計算N(x)\nx=";
cin>>x;
cout<<"N("<<x<<")=\n"<<nt.GetValue(x)<<endl;
if(x==0.0)
break;
}
return 0;
}