/**
  牛顿插值法

  牛顿递推公式：N_k(x) = N_k-1(x) + t_k(x) / f [x₀,x₁,..,x_k]

  基函数递推公式： t_i (x)  = (x - x _i ) * t_i-1 (x) 

  属性：插值计算法
  
   《数值计算方法与算法》第二版 - 科学出版社 P25

  代码维护：2007.04.18   pengkuny
**/

#include <iostream>
using namespace std;

float NewtonInterpolate(float px[], float py[], int n, float x)
{//px,py;插值点(Xi,Yi) n:插值点个数  x:待计算的点
    float *g = new float[n+1];

    //计算差商表个g[k],k=0,1,,n
    for (int i=0; i<n+1; i++)
    {
        g[i] = py[i];
    }
    for (int k=1; k<n+1; k++)
    {
        for (int i=n; i>=k; i--)
        {
            g[i] = (g[i] - g[i-1]) / (px[i] - px[i-k]);//g[i]用来暂时存放f[X(i-k), X(i)]
        }
    }

    float t = 1;//基函数
    float newton = py[0];
    for (int i=1; i<n; i++)
    {
        t = (x - px[i-1]) * t;//基函数的递推式
        newton = newton +  t * g[i];
    }

    delete g;
    return newton;
}

int main()
{
    float x;//插值
    float px[10];//已知(x0,y0),(x1,y1)
    float py[10];
    int n;//输入已知插值组数

    cout<<"输入插值组数:"<<endl;
    cin>>n;
    cout<<"输入"<<n<<"组已知插值数（X,Y）"<<endl;
    for(int i=0; i<n; i++)
    {
        cin>>px[i]>>py[i];
    }
    cout<<"输入插值:"<<endl;
    cin>>x;

    cout<<"牛顿插值结果:"<<NewtonInterpolate(px, py, n, x)<<endl;

    system("pause");
    return 0;
}