#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct data
{
        float x;
        float y;
}data;
data d[20];
int n;
float f(s,t)
{
        if(t==s+1)
                return (d[t].y-d[s].y)/(d[t].x-d[s].x);
        else
                return (f(s+1,t)-f(s,t-1))/(d[t].x-d[s].x);
}
float newton(float x,int n)
{
        int i,j;
        float y=d[0].y;
        float t=1.0;
        for(i=0;i<n;i++)
        {
                t=t*(x-d[i].x);
                y=y+t*f(0,i+1);
        }
        return y;
}
float lagrange(float x,int n)
{
        int i,j;
        float t=1.0;
        float y=0,y1=0;
        for(i=0;i<n;i++)
        {
                t=1.0;
                for(j=0;j<n;j++)
                {
                        if(j==i)
                                continue;

                        t=t*(x-d[j].x)/(d[i].x-d[j].x);
                }
                y=y+t*d[i].y;

        }
        return y;

}
int main()
{
        int flag;float x,y;
        printf("请输入节点的数目\n");
        scanf("%d",&n);
        printf("请输入要求的点x：\n");
        scanf("%f",&x);
        printf("请输入要插入的节点 本程序设定的节点数不大于20个 清输入：\n");
        int i;
        for(i=0;i<n;i++)
        {
                printf("输入点%d的x，y\n",i+1);
                scanf("%f,%f",&d[i].x,&d[i].y);
        }
        printf("请选择插值方法1为newton 2为lagrange 3为两种都计算\n");
        scanf("%d",&flag);
        if(flag==1)
        {
                y=newton(x,n);
                printf("插值结果y＝%f\n",y);

        }
        else if(flag==2)
                printf("插值结果y＝%f\n",lagrange(x,n));
        else
        {
                printf("插值结果y＝%f\n",newton(x,n));
                printf("插值结果y＝%f\n",lagrange(x,n));
        }
                       
return 0;