求离散点三角形的重心在哪里问题

来源：蜘蛛抓取(WebSpider) 时间：2022-11-23 10:38 标签： 三角形的重心在哪里

由于作者是一个初二蒟蒻，有一些地方可能存在问题，请多指教。喷轻点
你以为我会先讲插值吗？

所有数列都有规律——拉格朗日

先 $orz$ 拉格朗日一下：

约瑟夫·拉格朗日（Joseph-Louis Lagrange，）全名为约瑟夫·路易斯·拉格朗日，法国著名数学家、物理学家。1736年1月25日生于意大利都灵，1813年4月10日卒于巴黎。他在数学、力学和天文学三个学科领域中都有历史性的贡献，其中尤以数学方面的成就最为突出。
拉格朗日总结了18世纪的数学成果，同时又为19世纪的数学研究开辟了道路，堪称法国最杰出的数学大师。同时，他的关于月球运动（三体问题）、行星运动、轨道计算、两个不动中心问题、流体力学等方面的成果，在使天文学力学化、力学分析化上，也起到了历史性的作用，促进了力学和天体力学的进一步发展，成为这些领域的开创性或奠基性研究。

然后让我们想想为什么慢？因为我们知道的太多了。
我们发现求出 $f(x)$ 的部分好像是多余的，考虑直接求出 $f(k)$。
乍一看好像十分懵逼，我们一点一点地分析它。
首先显然 $L_n(x)$ 是一个 $n$ 次的多项式，然后再让我们分析一下 $\ell_i(x)$，我们可以发现它有一些神奇的性质：

所以每加入一个点，我们用 $O(n)$ 的时间复杂度计算出重心权 $w_i$，即可求出新的 $L_n(x)$。

于是就可以进行加入、撤销的操作了，它有向后稳定性。

这就是重心拉格朗日插值法（第二型）或是叫做真正的重心拉格朗日插值公式。它比重心拉格朗日插值法（第一型）更好计算，常数更小，向前稳定，并且勒贝格常数很小，用 $x_i=\cos(\frac{(2i+1)\pi}{2(n+1)})$ 就是切比雪夫插值节点插值效果好，可以很好地模拟给定的函数，使得插值点个数趋于无穷时，最大偏差趋于零。

艾萨克·牛顿（1643年1月4日—1727年3月31日）爵士，英国皇家学会会长，英国著名的物理学家，百科全书式的“全才”，著有《自然哲学的数学原理》、《光学》。

他在1687年发表的论文《自然定律》里，对万有引力和三大运动定律进行了描述。这些描述奠定了此后三个世纪里物理世界的科学观点，并成为了现代工程学的基础。
他通过论证开普勒行星运动定律与他的引力理论间的一致性，展示了地面物体与天体的运动都遵循着相同的自然定律；为太阳中心说提供了强有力的理论支持，并推动了科学革命。

在力学上，牛顿阐明了动量和角动量守恒的原理，提出牛顿运动定律。

在光学上，他发明了反射望远镜，并基于对三棱镜将白光发散成可见光谱的观察，发展出了颜色理论。他还系统地表述了冷却定律，并研究了音速。

在数学上，牛顿与戈特弗里德·威廉·莱布尼茨分享了发展出微积分学的荣誉。他也证明了广义二项式定理，提出了“牛顿法”以趋近函数的零点，并为幂级数的研究做出了贡献。

在经济学上，牛顿提出金本位制度。

然后我们定义差商（均差）的概念：即导数的近似值，对等步长的离散函数 $f(x)$ ，其 $n$ 阶差商就是它的 $n$ 阶差分与其步长的 $n$ 次幂的比值。 ——摘自

我们考虑存在未知点 $x$ 的差商，移项可得

取哪一个都会是 $0$，可以去掉。
实现的时候便可以增量构造，我们时刻维护 $x_n$ 结尾的 $n$ 个差商和多项式 $\prod(x-x_i)$ 即可，差商用定义的公式递推，多项式因为每次乘二项式，直接递推，两个东西都可以 $O(n)$ 维护。总复杂度为 $O(n^2)$。
不过它比拉格朗日插值更好的是，它可以插出多项式的系数。当给出的节点等距时，使用差分能达到更优的效果，其计算更加简便。

如果 $O(n\log^3 n)$还是满足不了大佬AKIOI的需求时，我们就继续换方法。

注意：以下内容可能引起不适，建议学过的同学学习。

【高能预警】下面的公式非常密集！！！

递归求解即可，时间复杂度 $O(n\log^2n)$，常数极大。

不过代码就不给了，因为我还没写出来

不过其实我们日常生活不会用到IOI不考，所以实用性不强，但是它可以解决一些毒瘤的问题。

我要回帖

更多关于 三角形的重心在哪里 的文章

 

随机推荐