#include <stdio.h>
#include <stdlib.h> 
#include <math.h> 
float lagrange(int n,float *x,float *y,float X);  //聲明拉格朗日插值函數
int main()
{
  int i;
  int t;
  float x[20];                 //最多20組成員數組
  float y[20];                 //最多20組成員對應的數據
  float X,Px;
    printf("    請輸入插值多項式的次數N\n");   
    scanf("    %d",&t);         //獲取多項式的次數t次
    t=t+1;
  for( i=0;i<t;i++)             //獲取各組數據,共t+1組,因為t+1個點惟一地確定t次多項式h(x)
  {
    printf("    請輸入x[%d]：\n",i);
    scanf("    %f",&x[i]);
    printf("    請輸入y[%d]：\n",i);
    scanf("    %f",&y[i]);
  }
  printf("    請輸入要計算的X的值：\n");  
  scanf("    %f",&X);            //獲取計算的X的值,應用中取x=0
  Px=lagrange(t,x,y,X);          //調用拉格朗日插值函數計算
  system("cls");
  printf("\n===計算結果如下=====\n\n");
  printf("    當 X=%.4f 時",X);  //輸出X的值
  printf("   Y=%.4f \n",Px);     //輸出計算結果
  
  return 1; 
  
}
float lagrange(int n,float *x,float *y,float X)   //定義拉格朗日插值函數,n為次數,x指針指向對應成員數組,                                            
                                                  //y指針指向對應成員的值的數組,X為計算多項式中X的取值
{
    float L,P=0.0;
    int j,k;
     for(k=0;k<n;k++)
      {
        L=1.0;
        for(j=0;j<n;j++)
          {
            if(j==k)
              continue;
            L*=(X-x[j])/(x[k]-x[j]);         //L為Lagrange插值基函數
          }
        P+=y[k]*L;                           //P為n次Lagrange插值多項式
     }
   return P;
}