拉格朗日插值

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

拉格朗日插值

拉格朗日插值,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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端儿

比较字母大小

任意给出两个英文字母,比较它们的大小,规定26个英文字母A,B,C.....Z依次从大到小。

15500
来自专栏python读书笔记

《python算法教程》Day10 - 平面最近点对问题平面最小点对问题介绍代码演示

今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点对的时间复杂度为O(nlogn)的算法。 平面最小点对问题介绍 在...

749120
来自专栏bboysoul

1167: C语言实验题――分数序列

描述:有一个分数序列:2/1, 3/2, 5/3, 8/5, 13/8, …编写程序求出这个序列的前n项之和。 输入:输入只有一个正整数n,1≤n≤10。 ...

12030
来自专栏尾尾部落

[剑指offer] 数值的整数次方 [剑指offer] 数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

9330
来自专栏武培轩的专栏

迅雷2019秋招后台开发编程题题解

有红黑两种颜色的方块积木,红色代表正数A,黑色代表负数B。选出17块积木排成一排,使得任意相邻7块积木之和都小于0。如何挑选才能使17块积木之和最大,最大值是多...

15330
来自专栏人工智能

Tensorflow下Char-RNN项目代码详解

前言 Char-RNN,字符级循环神经网络,出自于Andrej Karpathy写的The Unreasonable Effectiveness of Recu...

691100
来自专栏数据处理

TensorFlow入门1-minist

18130
来自专栏祥子的故事

python | pandas | 移动窗口函数rolling

78250
来自专栏Java 源码分析

平衡搜索树

2-3树 ​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子...

32190
来自专栏机器学习和数学

[编程经验] Tensorflow中的共享变量机制小结

今天说一下tensorflow的变量共享机制,首先为什么会有变量共享机制? 这个还是要扯一下生成对抗网络GAN,我们知道GAN由两个网络组成,一个是生成器网络G...

84930

扫码关注云+社区

领取腾讯云代金券