题解 P4525 【【模板】自适应辛普森法1】

Ebola

2018-06-20 17:08:36

Solution

#### 广告:[我的博客](http://ebola.blogwo.com/2018/06/20/%E8%BE%9B%E6%99%AE%E6%A3%AE%E7%A7%AF%E5%88%86-%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/) ## 导入 众所周知,对于计算机而言,给定具体数值的计算是非常简单的,但要让计算机实现公式推导,那是难上加难。可是,卡西欧计算器却有积分这么一项功能。你觉得是它内部实现了公式推导?那为什么它不输出它“推导”出的不定积分公式,而是只支持定积分求值呢?而且为什么输出的答案与人工带入积分公式算出的结果相差无几呢?本文就来探讨这一问题。 ## 知识预备 ### 1.函数的拟合 如果给定了一个奇怪的函数,我们可以用一个图像与它近似的初等函数来代替它,这样的过程称之为“拟合” ### 2.二次函数的定积分 对于一个二次函数F(x),它在[l,r]区间内的定积分值为(F(l)+4F(mid)+F(r))*(r-l)/6 ## 正文部分 我们可以把给定函数当做一个二次函数,然后直接套二次函数的定积分公式 这样的精度误差是非常大的,会算出一些离谱的答案。那我们考虑将函数分段 函数的每一段,我们都用一个二次函数去拟合它,得出这一段的近似值。如果我们把整个函数分成非常多段,那我们得出的值也就近似于答案了 分成非常多段?究竟是多少段? 一个显然的事情就是:如果我们分的段太少,答案会不精确;如果我们分的段太多,程序的运行时间会让人绝望 于是我们让程序进行一个“自适应”操作。即,如果这一段函数与拟合出的二次函数非常相似,那么我们直接把这一段当做二次函数,套公式算出结果;如果这一段与拟合出的二次函数不甚相似,那么我们把这一段分成两半,并递归进行这一过程 如何判断这一段函数与拟合出的二次函数的相似程度呢? 我们可以对整段、左半部分、右半部分分别套二次函数定积分公式进行计算,结果分别记作A,、L、R,若L+R与A相差的值不超过我们设定的精度了,那就认为这一段函数与拟合出的二次函数非常相似 这样计算的时间复杂度取决于程序的迭代次数,也就是给定函数与二次函数的相似程度。当然,也取决于你设定的精度,精度越低越快,但答案误差也越大,具体的精度选择要看题目的要求 ## 模板 ```cpp const double eps=精度要求; double F(double x){需要积分的函数} double simpson(double l,double r) { double mid=(l+r)/2; return (F(l)+4*F(mid)+F(r))*(r-l)/6; } double asr(double l,double r,double A) { double mid=(l+r)/2; double L=simpson(l,mid),R=simpson(mid,r); if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0; return asr(l,mid,L)+asr(mid,r,R); } double asr(double l,double r){return asr(l,r,simpson(l,r));} ``` ## 本题题解 直接往上面模板的F函数中输入本题给定函数,然后调用一次asr(l,r)即可