题目描述

题目描述
有形如：a x^3 + b x^2 + c x + d = 0ax
3
+bx
2
+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,da,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 -100−100 至 100100 之间），且根与根之差的绝对值 \ge 1≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 22 位。

提示：记方程 f(x) = 0f(x)=0，若存在 22 个数 x_1x
1
​
和 x_2x
2
​
，且 x_1 < x_2x
1
​
<x
2
​
，f(x_1) \times f(x_2) < 0f(x
1
​
)×f(x
2
​
)<0，则在 (x_1, x_2)(x
1
​
,x
2
​
) 之间一定有一个根。

输入格式
一行，44 个实数 a, b, c, da,b,c,d。

输出格式
一行，33 个实根，从小到大输出，并精确到小数点后 22 位。

样例

输入 #1复制
1 -5 -4 20
输出 #1复制
-2.00 2.00 5.00

算法1

错误算法

刚开始想的是先从-100-100中找最小的那一个，然后再逐步找，后来发现设置的check会将中间的值直接屏蔽掉
然后设想先把最小和最大的找出来，然后再分别进行+1,-1（根据题干解的范围）来二分找中间值，发现仍会屏蔽

C++ 代码

#include <bits/stdc++.h>
using namespace std;
double a,b,c,d;
double l,r;
bool check(double x)
{
    if ((a*x*x*x+b*x*x+c*x+d)*(a*l*l*l+b*l*l+c*l)<=1e-7) return true;
    if ((a*x*x*x+b*x*x+c*x+d)*(a*l*l*l+b*l*l+c*l)>1e-7) return false;
    return true;
}
int main()
{
    scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
    const double eps = 1e-6;
    l=-1e2,r=1e2;
    for (int i=1;i<=3;i++)
    {
        while(r-l>eps)
        {
            double mid = (l+r)/2;
            if (check(mid)) r = mid;
            else l = mid;
        }
        printf("%.2lf ",l);
        r = 1e2;
    }
}

算法2

(暴力枚举+二分)

在算法1的基础上为了使不被屏蔽而从-100开始直接在两个差为1的数之间二分（根据题目条件）（此题有区别于机器人跳跃）

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int s;   //用来存储找到了几个解
double a,b,c,d;
double l,r;
double f(double x)
{
    return a*x*x*x+b*x*x+c*x+d;    //减少一下代码量
}
bool check(double a)
{
    if (f(a)*f(l)<=1e-7) return true;
    return false;    //一个函数返回值只有一个
}
int main()
{
    scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
    const double eps = 1e-3;  //根据题目要求来，此处是0.01,但一般要再往后进一两位
    for (int i=-100;i<=100;i++)
    {
        l = i;
        r = i+1;   //看题干条件，两个解的绝对值之差大于等于1，题目条件一般没有没用的，不要自己以为没用
        if (!f(l))  //浮点数为了求准确一般这么表示取0（1e-7总有误差，一般都是if大于和小于再取else判断为0的）
        {
            printf("%.2lf ",l);
            s++;
        }
        if (f(l)*f(r)<0)  //为什么不能写f(l)*f(r)<1e-7????  :             //好吧，是我记错了，<=1e-6是判断是否为0的，小于0常用else判断
        {
            while (r-l>eps)
            {
                double mid = (l+r)/2;
                if (check(mid)) r = mid;
                else l = mid;
            }
            printf("%.2lf ",r);
            s++;
        }
        if (s==3) break;
    }
    return 0;
}

算法3

(暴力枚举+极限思想) $O(n^2)$

因为n最多只到100，可以直接暴力枚举（算法2实际上是枚举的优化，不要忘了基本方法）

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double a,b,c,d;
    scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
    for (int i=-100;i<=100;i++)
    {
        double l=i+1e-3;
        double y1 = a*i*i*i+b*i*i+c*i+d;
        double y2 = a*l*l*l+b*l*l+c*l+d;
        if ((y1<=0 and y2>=0) or (y1>=0 and y2<=0))  //所以为什么不能写1e-7???  ： 同上
        {
            double x = (l+i)/2;
            printf("%.2lf ",x);
        }
    }
}

算法4

(数学思想)

结合数学思想，求导（溯源）

先求二次的导数，找出满足0的点，再根据单调性求，此处不再写代码