鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

拉格朗日插值

来源:互联网 作者:佚名 时间:2018-01-25 11:34
存在性和唯一性的证明以后再补。。。。 拉格朗日插值 拉格朗日插值,emmmm,名字挺高端的 :joy: 它有什么应用呢? 我们在FFT中讲到过 设$n-1$次多项式为 $y=\sum_{i=0}^{n-1}a_i x^i$ 有一个显然的结论:如果给定$n$个互不相同的点$(x,y)$,则该$n-1$次多项

存在性和唯一性的证明以后再补。。。。

拉格朗日插值

拉格朗日插值,emmmm,名字挺高端的:joy:

它有什么应用呢?

我们在FFT中讲到过

设$n-1$次多项式为

$y=\sum_{i=0}^{n-1}a_i x^i$

有一个显然的结论:如果给定$n$个互不相同的点$(x,y)$,则该$n-1$次多项式被唯一确定

那么如果给定了这互不相同的$n$个点,

利用拉格朗日插值,可以在$O(n)$的时间内计算出某项的值,还可以在$O(n^2)$的时间复杂度内计算出给定的$x$所对应的$y$

那么如何计算呢?

公式

不啰嗦了,直接给公式吧,至于这个公式怎么来的以后再补充

若对于$n-1$次多项式,给定了$n$个互不相同的$(x,y)$

那么对于给定的$x$,第$i$项的值为

$l(i)=y_i\prod_{j=1,j\neq i}^{n} \dfrac{x-x_j}{x_i-x_j}$

所对应的$y$为

$y=\sum_{i=1}^{n} l(i)$

$=\sum_{i=1}^{n}y_i\prod_{j=1,j\neq i}^{n}\dfrac{x-x_j}{x_i-x_j}$

利用这个公式,就可以进行计算啦

代码

 

#include<cstdio>
int x[1001],y[1001];
int N,ans=0;
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&x[i],&y[i]);
    int X;//待求的x 
    scanf("%d",&X);
    for(int i=1;i<=N;i++)
    {
        int tmp=y[i];
        for(int j=1;j<=N;j++)
        {
            if(i==j) continue;
            tmp=tmp*(X-x[j])/(x[i]-x[j]);
        }
        ans+=tmp;
    }
    printf("%d",ans);
    return 0;
}

 

上一篇:c/c++ 贪吃蛇控制台版
下一篇:群论入门
网友评论
<