一元三次方程求解（数学、二分）

https://www.luogu.com.cn/problem/P1024

1 -5 -4 20

-2.00 2.00 5.00

记方程f(x)=0，若存在2个数x1?和x2?，且x1?<x2?，f(x1?)×f(x2?)<0，则在(x1?,x2?)之间一定有一个根。

这题解法比较多

因为区间很大，所以可以二分。

题目保证三个答案都在[-100,100]范围内，且两个根的差的绝对值>=1，所以每一个大小为1的区间里至多有1个解。

当区间的两个端点的函数值异号时区间内一定有一个解，这个时候我们可以在区间内进行二分查找ans，如果同号则该区间一定没有解。

刚开始遍历i从-10000到10000了，然后i再除以100当成x的值，没想到这样显示TLE了。。。

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <sstream>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
const double eps = 1e-8;
const double PI = acos(-1);

double a,b,c,d;//开成double吧，免得出错 
vector<double> ans;
double f(double x)
{
    return a*x*x*x+b*x*x+c*x+d;
}

double solve(double x1,double x2)    //在x1和x2中二分找答案 
{
    double L=x1,R=x2;
    while(R-L>1e-4)    //这里的eps一般要比题中要求的精度（1e-2）多两位。
    {
        double mid=(L+R)/2;
        double t1=f(L);
        double t2=f(mid);
        double t3=f(R);
        if(t2==0) return mid;
        if(t1*t2<0) R=mid;
        else if(t2*t3<0) L=mid;
    }
    return (L+R)/2;//返回L,R,(L+R)/2都行
}

int main()
{
    #ifdef DEBUG 
    freopen("sample.txt","r",stdin);
    #endif
    
    scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
    double pre=f(-100.0);
    for(int i=-100;i<=100;i++)
    {
        double t=f(i);
        if(t!=0)
        {
            if(t*pre<0) ans.push_back(solve(i-1,i));
        }
        else ans.push_back(i);
        pre=t;
    }
    for(int i=0;i<3;i++)
        printf(i==2?"%.2f\n":"%.2f ",ans[i]);
    
    return 0;
}

下面是我看别的大佬写的

盛金公式：

#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
     double a,b,c,d;
     double as,bs,t,si;
     double x1,x2,x3;
     cin>>a>>b>>c>>d;
     as=b*b-3*a*c;
     bs=b*c-9*a*d;
     t=(2*as*b-3*a*bs)/(2*sqrt(as*as*as));
     si=acos(t);
     x1=(-b-2*sqrt(as)*cos(si/3))/(3*a);
     x2=(-b+sqrt(as)*(cos(si/3)+sqrt(3)*sin(si/3)))/(3*a);
     x3=(-b+sqrt(as)*(cos(si/3)-sqrt(3)*sin(si/3)))/(3*a);
     cout<<fixed<<setprecision(2)<<x1<<" ";
     cout<<fixed<<setprecision(2)<<x3<<" ";
     cout<<fixed<<setprecision(2)<<x2<<" ";
     return 0;
}

最后是EarthGiao大佬写的题解：

导数+勘根定理+牛顿迭代.

先对函数求导,f‘(x)=3ax^2+2*bx+c.

然后直接求根公式求f‘(x)=0的点,也就是函数极点.

这题保证有三个不定根,所以有两个单峰.

我们分别设这两个点为p,q.

然后显然的必有三个根在[-100,p),[p,q],(q,100]三个区间内 (两极点间必定存在零点,勘根定理).

然后用神奇的牛顿迭代法多次迭代就好了.

#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-4
using namespace std;
double x1,x2,x3,a,b,c,d;
double f(double x){return a*x*x*x+b*x*x+c*x+d;}
double df(double x){return 3*a*x*x+2*b*x+c;}
double slove(double l,double r)
{
    double x,x0=(l+r)/2;
    while(abs(x0-x)>eps)
      x=x0-f(x0)/df(x0),swap(x0,x);
    return x;
}
int main()
{
    cin>>a>>b>>c>>d;
    double p=(-b-sqrt(b*b-3*a*c))/(3*a);
    double q=(-b+sqrt(b*b-3*a*c))/(3*a);
    x1=slove(-100,p),x2=slove(p,q),x3=slove(q,100);
    printf("%.2lf %.2lf %.2lf",x1,x2,x3);
    return 0;
}

-