拉格朗日插值

直接上公式

简单的讲 ，这个玩意就是在给你若干个 f(xi) = yi 的结果 算出f(k) 的结果

//最朴素的实现方法 验证下这个公式的结果 
#include <bits/stdc++.h>
using namespace  std;
int main(){
    int n;
    //输入n 个点的坐标
    cin>>n;
    vector< pair<double ,double > > node;
    for(int i = 0 ; i < n; ++i){
        int x,y;
        cin>>x>>y;
        node.push_back(make_pair(y,x));
    }
    while(1){
        double k;
        //f(k) 的 k
        cin>>k;
        if(k == 0 ){
            break;
        }
        double result = 0 ;
        for(int i = 0 ; i < node.size() ; ++i){
            double tem = node[i].first;
            for(int j = 0 ; j < node.size() ; ++j){
                if(i == j){
                    continue;
                }
                tem *= (k - node[j].second) / (node[i].second - node[j].second) ;
            }
            result += tem;
        }
        cout<<"K: " << k  << "  result : " <<result<<endl;
    }
}

这是输入 显而易见 f(x) = x^2
3
1 1
2 4
3 9
3
4
5

这是输出 显而易见 这个公式很好用
K: 3 result : 9
K: 4 result : 16
K: 5 result : 25

//todo. 关于程序实现增加一些乘法逆元

关于证明 暂时还不会