三分法

$Daily English

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

---

知识点：

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

---

0x00 题目：

洛谷p3382:
https://www.luogu.com.cn/problem/P3382

0x01 三分法

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

解释：
在[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)的值

原理：

---

0x03 解题代码：

#洛谷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; }

总结

以上是生活随笔为你收集整理的三分法+秦九昭算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。