自适应辛普森法

二次函数\(f(x)\)的积分公式：

\[\int_{l}^r f(x)dx=\frac{(r-l)(f(l)+f(r)+4f(\frac{l+r}{2})}{6} \]

自适应辛普森法是普通辛普森法的改良，用于求一般函数的积分。

实现方法：

设函数为\(f(x)\)，solve(l,r)表示\(f(x)\)在\([l,r]\)上的积分。

先用二次函数积分公式计算其在\(l,r\)上的积分，和\([l,mid]\),\([mid,r]\)的积分，如果误差\(\leq \exp\)则这段函数和二次函数很接近，直接返回结果。

否则递归算\([l,mid],[r,mid]\)。

double simpson(double l, double r) {
  double mid = (l + r) / 2;
  return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;  // 辛普森公式
}
double asr(double l, double r, double eqs, double ans) {
  double mid = (l + r) / 2;
  double fl = simpson(l, mid), fr = simpson(mid, r);
  if (abs(fl + fr - ans) <= 15 * eqs)
    return fl + fr + (fl + fr - ans) / 15;  // 足够相似的话就直接返回
  return asr(l, mid, eqs / 2, fl) +
         asr(mid, r, eqs / 2, fr);  // 否则分割成两段递归求解
}