题解 P1024 【一元三次方程求解】

_ZZH · 2018-08-04 14:57:13 · 题解

我猜有一半以上的盛金公式……

我这里想写求导+二分答案。

好像有大佬写过了，我想带大家来分析一下这道题的处理过程：

我们观察一元三次方程的大致图像： 　　　如图便是一个标准情况下的三次函数图像。当a>0时通过观察我们会发现从左到右的趋势是：升——降——升。而当a<0时情况相反。

　　　当然了，输入保证方程有三个解，为了方便观察解的分布，我们绘制样例的图像：

　　我们发现三个解分别分布在其三个单调区间内，因此我们可以在每个单调区间内二分。

　　接下来一步是如何求 其单调区间，显然其单调区间为：[-100,x1],[x1,x2],[x2,100];关键就是求函数的两极值点。

　　考虑求导（逃

　　导函数f’(x)=3ax^2+2bx+c，求其两零点（题目保证解的存在性），由公式法知：　

　　 x1=(-2b+sqrt(4bb-12ac))/(6a);

　　 x2=(-2b-sqrt(4bb-12ac))/(6a);

　　对于a<0的情况，为了统一将a变为-a，其余系数也乘-1，方程-ax^3-bx^2-cx-d=0 仍成立，不影响答案。

　　对于增区间和减区间分别二分求解即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double a,b,c,d;
const double eps=0.001;
double judge(double x)
{
    return a*x*x*x+b*x*x+c*x+d;//带入求值
}
double find_up(double l,double r)
{
    while(fabs(r-l)>eps)//控制精度
    {
        double mid=(r+l)/2.0;
        if(judge(mid)<0)l=mid;
        else r=mid;
    }
    return l;
}
double find_down(double l,double r)
{
    while(fabs(r-l)>eps)
    {
        double mid=(r+l)/2.0;
        if(judge(mid)<0)r=mid;
        else l=mid;
    }
    return r;
}
int main()
{
    cin>>a>>b>>c>>d;
    if(a<0)
    {
        a=-a;
        b=-b;
        c=-c;
        d=-d;
    }
    double 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("%.2f ",find_up(-100.0,x2));
    printf("%.2f ",find_down(x2,x1));
    printf("%.2f",find_up(x1,100.0));
}