[NOIP2001 提高组] 一元三次方

• 题目描述
• 思路
• code

tag：数学，二分查找
题目链接：洛谷P1024: [NOIP2001 提高组] 一元三次方

题目描述

思路

先对三次函数求导得到二次函数 3ax2+2bx+c=03ax^2 + 2bx + c = 03ax2+2bx+c=0
然后利用求根公式计算出两个极值点 x1x1x1 x2x2x2
将整个区间划分为三个单调区间 [−100,x1],[x1,x2],[x2,100][-100, x1],[x1,x2],[x2,100][−100,x1],[x1,x2],[x2,100]，在这三个区间中分别使用二分。
令 f(x)=该一元三次函数f(x) = 该一元三次函数f(x)=该一元三次函数
每次判断 f(left)f(left)f(left) * f(mid)f(mid)f(mid)
f(left)f(left)f(left) * f(mid)<=0:f(mid)<= 0 :f(mid)<=0: 说明此时两个函数值异号，让 right=midright=midright=mid
否则说明两个函数值同号，让 left=midleft = midleft=mid

code

#include 
using namespace std;const double eps = 1e-4;
double a,b,c,d;double calc(double x) {return a*x*x*x + b*x*x + c*x + d;
}void bsearch(double l, double r) {while (r - l > eps) {double mid = (l + r) / 2;if (calc(mid) * calc(l) <= 0) r = mid;else l = mid;}printf("%.2lf ", l);
}int main() {scanf("%lf%lf%lf%lf",&a,&b,&c,&d);// 3ax^2 + 2bx + cdouble x1 = (-2*b - sqrt(4*b*b - 12*a*c)) / (6 * a);double x2 = (-2*b + sqrt(4*b*b - 12*a*c)) / (6 * a);// printf("%lf %lf\n", x1, x2);bsearch(-100, x1);bsearch(x1, x2);bsearch(x2, 100);return 0;
}