NOIP 2001 一元三次方程求解(二分||盛金公式)

喜欢ヅ旅行 2022-05-17 10:55 203阅读 0赞

题目描述

有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。  
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)\*f(x2)<0，则在(x1，x2)之间一定有一个根。

输入

每个测试文件只包含一组测试数据，每组输入四个实数a，b，c，d，表示一元三次方程中的各项的系数。

输出

对于每组输入数据，由小到大依次在同一行输出这三个实根（根与根之间留有一个空格），并精确到小数点后2位。

解法一：一个实根的左右两个点的乘积一定是<0的 那么其实也就满足了单调性，可以用二分求解，不断二分直到根的位置。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e+2;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-3;
    double a,b,c,d;
    
    double calc(double x)
    {
        return a*x*x*x+b*x*x+c*x+d;
    }
    
    void slove()
    {
        double l,r;
        int cnt=0;
        for(int i=-100;i<=100;i++)
        {
            l=i*1.0,r=(i+1)*1.0;
            if(calc(l)==0){
                printf("%.2lf ",l);
                cnt++;
            }
            else if(calc(l)*calc(r)<0){
                while(r-l>=eps){
                    double mid=(l+r)/2.0;
                    if(calc(mid)*calc(l)<0)
                        r=mid;
                    else l=mid;
                }
                printf("%.2lf ",l);
            }
            if(cnt==3) break;
        }
        printf("\n");
    }
    
    int main()
    {
        scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
        slove();
        return 0;
    }

方法二：范盛金公式

[参考百度百科][Link 1]

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e+2;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-3;
    double a,b,c,d;
    /**
    盛金公式
    */
    
    int main()
    {
        double x1,x2,x3,temp;
        scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
        double A=b*b-3*a*c;
        double B=b*c-9*a*d;
        double C=c*c-3*b*d;
        double del=B*B-4*A*C;
        //Δ=B2－4AC>0时是虚根
        if(A==B&&A==0)
        {
            x1=x2=x3=-b/(3*a);
        }else if(del==0){
            x1=-b/a+B/A;
            x2=x3=(-B/A)/2;
        }else if(del<0){
            double T=(2*A*b-3*a*B)/(2*A*sqrt(A));
            double _xt=acos(T);
            double xt=_xt/3;
            x1=(-b-2*sqrt(A)*cos(xt))/(3*a);
            x2=(-b+sqrt(A)*(cos(xt)+sqrt(3)*sin(xt)))/(3*a);
            x3=(-b+sqrt(A)*(cos(xt)-sqrt(3)*sin(xt)))/(3*a);
        }
        if(x1>x2)
        {
            temp=x1;
            x1=x2;
            x2=temp;
        }
        if(x1>x3)
        {
            temp=x3;
            x3=x1;
            x1=temp;
        }
        if(x2>x3)
        {
            temp=x3;
            x3=x2;
            x2=temp;
        }
        printf("%.2lf %.2lf %.2lf\n",x1,x2,x3);
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E4%B8%80%E5%85%83%E4%B8%89%E6%AC%A1%E6%96%B9%E7%A8%8B%E6%B1%82%E6%A0%B9%E5%85%AC%E5%BC%8F/10721952