/**
拉格朗日插值计算
拉格朗日插值公式：
                n     n
  Pn(x(i))= ∑〔  ∏（ x-x(j)）/（x(k)-x(j)） 〕y(k)
               k=0   j=0,
                      j≠k
 
  属性：插值计算法
                                                                           n
  精度(局部截断误差)：| f(x) - Pn(x) | = [f(ε)] / (n+1)!  ∏  ( x - x(k) ) 
 (注：其中[f(ε)]为f(ε)第n+1次求导的表达式)              k=0  
                                        
 《数值计算方法与算法》第二版 - 科学出版社 P19

  代码维护：2007.04.18   pengkuny
**/

float Lagrange(float px[], float py[], int n, float x)
{//px,py:插值点(Xi,Yi) n:插值点个数  x:待计算的函数点
    float y = 0;
    for(int k=0; k<n; k++)//k控制Lagrange基函数序列
    {
        float tmp = 1;//tmp表示Lagrange基函数
        for(int i=0;i<n;i++)
        {
            if(i!=k)
            {
                tmp = tmp * (x-px[i])/(px[k]-px[i]);  //key step
            }
        }
        y = y + py[k]*tmp;
    }
    return y;
}

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<<"Lagrange插值结果:"<<Lagrange(px, py, n, x)<<endl;

    system("pause");
    return 0;
}