鏈接: 原題
題意就是給定一個(gè)區(qū)間，[l,r],保證函數(shù)中間有凸點(diǎn)，求導(dǎo)+秦九韶算法+二分。

秦九韶算法的公式，可將多項(xiàng)式的計(jì)算時(shí)間復(fù)雜度降到o(n)

#include <bits/stdc++.h> using namespace std; const int N = 100; const double eps = 1e-10; int n; double l, r, a[N]; //秦九韶公式的計(jì)算，每一個(gè)多項(xiàng)式的值都根據(jù)比自己高一次的值來進(jìn)行計(jì)算 inline double f(double x) {double t[N];t[n] = a[n];for(int i = n - 1; i >= 0; --i) {t[i] = t[i + 1] * x + a[i];}return t[0]; } //求導(dǎo) 等于求斜率 初中的公式 double check(double x) {double dx = eps;double dy = f(x + dx) - f(x);return dy / dx; } signed main() {scanf("%d%lf%lf", &n, &l, &r);for(int i = 0; i <= n; ++i) scanf("%lf", &a[n - i]);double ok;while(r - l > eps) {ok = (l + r) / 2;if(check(ok) > 0) l = ok;//一定是l=ok 往右走 往上爬else r = ok;}printf("%.5lf", ok);return 0; }

總結(jié)

以上是生活随笔為你收集整理的二分+秦九韶算法 求凸点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。