晚上训练的时候，王老师给大家讲授（普及）了一下拉格朗日插值法。
这是一个非常美妙的计算多项式的值的算法，可惜我迟到了一句也没有听到。感谢善良的王老师…又给我讲了一遍….
好了，下面就要开始口胡了👇：
首先拉格朗日插值法一种非常神奇的求多项式的值的方法。
就像解多元多次方程组一样，已知多个函数的值，可以求出指定的多项式的值。
内容
对某个多项式，已知有给定的k + 1个取值点
\[(x_0, y_0),\ldots,(x_k,y_k)\]其中，\(x_j\)对应着自变量的位置，\(y_j\)对应着这个函数在这个位置的函数值。
则：
\[L(x) := \sum_{j=0}^ky_jl_j(x)\]基本多项式（插值基函数）\(l_j(x)\)本体：
\[l_j(x) := \frac{(x-x_0)}{(x_j-x_0)}\cdots\frac{(x-x_{j-1})}{(x_j-x_{j-1})}\frac{(x-x_{j+1})}{(x_j-x_{j+1})}\cdots\frac{(x-x_k)}{(x_j-x_k)}\]验证的方法也很简单：把\(x_0,x_1,x_2,\cdots,x_k\)带进去就可以…因为对于\(l_j(x)\)，除了\(x_j\)，其他的数带进去都为0。
x代码的实现
#include <cstdio>
#define MAXN 100000 + 5
using namespace std;
struct point {
double x, y;
}list[MAXN];
int n, m, k;
double x;
double lag(point *list, int num, double x) {
double ans = 0, foo = 1.0;
for (int i = 1; i <= num; ans += list[i].y * foo, foo = 1.0, i++) //累加累积的过程
for (int j = 1; j <= num; j++)
if (i != j)
foo *= (x - list[j].x) / (list[i].x - list[j].x);
return ans;
}
int main() {
scanf("%d", &n);
scanf("%d", &m);
for(int i = 1; i <= n; scanf("%lf%lf", &list[i].x, &list[i].y), i++);
while( m-- ) //询问
scanf("%lf", &x), printf("%lf\n", lag(list, n, x));
return 0;
}代码大概就是这样…为什么没有具体题目呢？因为很多题目都牵涉到更难的知识…毕竟我现在还是太菜了…加油吧…
本文主要参考:维基百科