三分法+秦九昭算法

港控/mmm° 2023-07-21 06:19 22阅读 0赞

# 三分法 #

$Daily English

> 神话是大众的梦想，梦想是一个人的神话。  
> Myths are public dreams,dreams are private myths.

--------------------

知识点：

*  三分法
 *  秦九昭算法
 *  三分法模板

--------------------

## 0x00 题目： ##

洛谷p3382:  
[https://www.luogu.com.cn/problem/P3382][https_www.luogu.com.cn_problem_P3382]

## 0x01 三分法 ##

问题：值序列构成的图像具有凸性或凹性时 求解最值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]  
解释：  
在\[l,r\]区间中找一个值x，使得f(x) = max。可以用三分法来求解这个x。  
基本思想是：将\[l,r\]区间分成三段不断逼近。区间分成三段所以需要确定两个点。  
这两点我们习惯性把它们命名为：lmid，rmid。  
这两点的值很好确定:  
左边（lmid）： l + 区间长度的1/3  
右边（rmid）： r - 区间长度的1/3

tmp = (r - l) / 3.0;
     lmid = l + tmp;
     rmid = r - tmp;

如果f(lmid) < f(rmid):  
那么lmid之前部分**对求解的x没有影响**，  
所以此时可以更新：  
l = lmid。  
否则，更新:r = rmid。

**如果理解不了，自己画一个图好好体会。**

--------------------

**如果凸性或凹性图像的方程是一个N次多项式，就要结合秦九昭算法来求解f(x)。即三分过程中，f(lmid) ， f(rmid)具体的值要使用秦九昭算法来求解**

--------------------

## 0x02 秦九昭算法： ##

问题：求解N次多项式f(x)的值  
![在这里插入图片描述][20200402222523234.png]  
原理：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70 1]

--------------------

## 0x03 解题代码： ##

[\#洛谷p3382][https_www.luogu.com.cn_problem_P3382] \# Ac\_code:

#include <bits/stdc++.h>
    using namespace std;
    const double eps = 1e-6;
    const int N = 15;
    double a[N];
    int n;
    double l,r;
    
    //秦九昭算法：求解N次多项式f(x)的值
    double check(double x)
    {
        
        double res = a[n];
        for(int i = n-1; i >= 0; i--)
        {
        
            res = res * x + a[i];
        }
        return res;
    }
    int main()
    {
        
        scanf("%d%lf%lf",&n,&l,&r);
        for(int i = n; i >= 0; i--)
        {
        
            scanf("%lf",&a[i]);
        }
        //三分法:值序列构成的图像具有凸性或凹性时求最值
        while(r-l > eps)
        {
        
            double tmp = (r - l) / 3.0;
            double lmid = l + tmp;
            double rmid = r - tmp;
            if(check(lmid) < check(rmid))
            {
        
                l = lmid;
            }
            else
            {
        
                r = rmid;
            }
        }
        printf("%.5lf\n",l);
        return 0;
    }

[https_www.luogu.com.cn_problem_P3382]: https://www.luogu.com.cn/problem/P3382
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]: /images/20230528/daa3364b12814b59aa9107180289f3dc.png
[20200402222523234.png]: /images/20230528/024c0e0e23da4bbc99514442f2cd851d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70 1]: /images/20230528/48e522a26eb54baf868298257f74d9ce.png