[板子] 自适应辛普森法

某谷居然有这个板子 震惊


Simpson公式如下:

$ \int_{a}^{b}{f(x) dx} \approx f(a) + f(b) + 4 f(\frac{a + b}{2}) $

直接这样求精度显然不够。

我们可以求Simpson(l,r)以及Simpson(l,mid) + Simpson(mid,r),如果两者相差较小则返回,否则两边递归下去。

Code

Luogu P4525

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cmath>
const double eps = 1e-12;
double a,b,c,d;
struct ASR
{
double f(double x)
{
return (c * x + d) / (a * x + b);
}
double simpson(double a,double b)
{
double mid = (a + b) / 2.0;
return ((b - a) / 6.0) * (f(a) + f(b) + 4.0 * f(mid));
}
double asr(double l,double r,double ans)
{
double mid = (l + r) / 2.0,L = simpson(l,mid),R = simpson(mid,r);
if(std::fabs(ans - L - R) < eps) return ans;
return asr(l,mid,L) + asr(mid,r,R);
}
}A;
int main()
{
double l,r;scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
printf("%.6lf\n",A.asr(l,r,A.simpson(l,r)));
return 0;
}