题解 P3382 【【模板】三分法】

· · 题解

前置技能：秦九韶定理（转自百度百科）

注：“韶”字念“[sháo]”而不念“ [zhāo] ”我这个蒟蒻就念错了15年〇6个月

一般地，一元n次多项式的求值需要经过[n（n+1）]/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。

把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式 

   f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0] 　　

        =(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0] 　　

        =((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0] 　　

        =...... 　　

        =(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0]. 　　

求多项式的值时，首先计算最内层括号内一次多项式的值，即 　　*ans[1]=a[n]x+a[n-1]** 　　然后由内向外逐层计算一次多项式的值，即 　　

        v[2]=v[1]x+a[n-2] 　　

        v[3]=v[2]x+a[n-3]

         　　...... 　　

        v[n]=v[n-1]x+a[0]

接下来是裸的三分操作

#include<bits/stdc++.h>
#define eps 1e-8
#define rep(i,x,y) for(register int i = x;i <= y;++i)
#define dwn(i,x,y) for(register int i = x;i >= y;--i)
#define N 14
using namespace std;
double l,r,a[N];
int n;

double check(double x)
{
    double ans = 0;
    dwn(i,n,0)
        ans=ans*x+a[i];//秦九韶公式
    return ans;
}

int main()
{
    scanf("%d",&n);
    scanf("%lf%lf",&l,&r);
    rep(i,0,n)
        scanf("%lf",&a[n-i]);
    while(r-l>eps)
    {
        double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
        if(check(mid1)>check(mid2))
            r=mid2;
        else 
            l=mid1;
    }
    printf("%.5lf",l);
    return 0;
}