题解 P4525 【【模板】自适应辛普森法1】
Ebola
2018-06-20 17:08:36
#### 广告:[我的博客](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)即可