C++ 代码

/* 输入多项式次数n，再输入n+1个点，就会输出一个多项式经过输入的点（不推荐用线上编译器）*/
#include <bits/stdc++.h>
using namespace std;
#define int double
#define integer long long
int a[2010],la;
int b[2010],lb;
int c[2010],lc;
int d[2010],ld;
int e[2010],le;
int f[2010],lf; 
//输入值x 
int x[2010];
//输入值 l(x)
int y[2010]; 
//langrange多项式次数 
integer n;
//c和d的乘积,e为结果 
void product(){
    le=lc+ld;
    for(integer i=0;i<=lc;++i){
        for(integer j=0;j<=ld;++j){
            e[i+j]+=c[i]*d[j];
        }
    }
    return; 
}
//c和d的和，e为结果 
void add(){
    le=max(lc,ld);
    for(integer i=0;i<=le;++i){
        e[i]=c[i]+d[i];
    }
    return;
}
//整数*多项式 
void integer_product(int u,int z[],int lz){
    for(integer i=0;i<=lz;++i){
        z[i]*=u;
    }
}
//把一个数组 z 拷贝到 w 
void memset_set(int z[],int &lz,int w[],int &lw){
    lz=lw;
    memset(z,0,sizeof(z));
    for(integer i=0;i<=lz;++i){
        z[i]=w[i];
    }
}
//拉格朗日 
void lagrange(){
    for(integer i=0;i<=n;++i){
        for(integer j=0;j<=n;++j){
            if(j==i){
                continue;
            }
            memset(c,0,sizeof(c));
            lc=1;
            c[0]=-x[j];
            c[1]=1;
            memset_set(d,ld,a,la);
            integer_product(1.0/(x[i]-x[j]),c,lc);
            memset(e,0,sizeof(e));
            le=0;
            product();
            memset_set(a,la,e,le);
        }
        integer_product(y[i],a,la);
        if(y[i]==0){
            la=0;
        }
        lc=0;
        ld=0;
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d)); 
        memset_set(c,lc,a,la);
        memset_set(d,ld,b,lb);
        memset(e,0,sizeof(e));
        le=0;
        add();
        memset_set(b,lb,e,le);
        la=0;
        memset(a,0,sizeof(a));
        a[0]=1;
    }
    memset_set(e,le,b,lb);
    return; 
}
signed main(){
    lb=0;
    b[0]=0;
    la=0;
    a[0]=1;
    cin>>n;
    printf("ex.\nx y\ninput(%d):\n",n);
    for(integer i=0;i<=n;++i){
        cin>>x[i]>>y[i];
    }
    lagrange();
    cout<<le<<endl;
    for(integer i=le;i>=0;--i){
        cout<<"+("<<e[i]<<")"<<"*x^"<<i<<" ";
    }
    return 0;
}