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

· · 题解

自适应辛普森法的模板。

积分的朴素求法就是用很多个小矩形来近似，但这样精度和时间都不高，考虑用其它的方法。

自适应辛普森发就是用二次函数来近似的积分。

假设用来近似的二次函数为g(x)=ax^2+bx+c。

那么函数f(x)=x^n的原函数即为：F(x)={1\over n+1}x^{n+1}，证明如下：

由定义得，只需证明如下式子：

F'(x)=f(x)=x^n

因为有公式：

f(x)=x^n,f'(x)=nx^{n-1}

所以:

F'(x)=[{1\over n+1}\cdot (n+1)]x^{n+1-1}=x^n

那么我们就可以得到：

f_1(x)=x^2\rightarrow F_1(x)={1\over 3}x^3 f_2(x)=x\rightarrow F_2(x)={1\over 2}x^2 f_3(x)=c\rightarrow F_3(x)=x g(x)=af_1(x)+bf_2(x)+cf_3(x)

所以，由牛顿-莱布尼茨公式可以得到：

\int_l^r g(x)dx=\int_l^r [af_1(x)+bf_2(x)+cf_3(x)]dx =a\int_l^rf_1(x)dx+b\int_l^rf_2(x)dx+c\int_l^rf_3(x)dx =a\cdot F_1(r)|_l^r+b\cdot F_2(r)|_l^r+c\cdot F_3(r)|_l^r ={a(r^3-l^3)\over 3}+{b(r^2-l^2)\over 2}+{c(r-l)}

胡乱化简，最后得到：

(r-l)[al^2+bl+c+ar^2+bl+c+4({al^2+2alr+ar^2\over 4}+{bl+br\over 2}+c)]\over 6 ={(r-l)g(r)+g(l)+4g({l+r\over 2}) \over 6} \approx {(r-l)f(r)+f(l)+4f({l+r\over 2}) \over 6}

这样我们就得到自适应辛普森法的公式啦！

对于这道题，直接套公式即可。

但是这样精度可能会不够，我们就二分区间，直到达到精度就返回，详见代码吧：

#include <iostream>
#include <cstdio> 
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

double a, b, c, d, L, R;

inline double f(double x) {
    return (c * x + d) / (a * x + b);
}

inline double simpson(double l, double r) {
    return (f(r) + f(l) + 4 * f((l + r) / 2)) * (r - l) / 6;
}

inline double getans(double l, double r) {
    double mid = (l + r) / 2;
    if (fabs(r - l) <= 1e-5) return simpson(l, r);
    return getans(l, mid) + getans(mid, r);
}

int main() {
    scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &L, &R);
    printf("%.6lf", getans(L, R));
    return 0;
}