洛谷题解——P1024：一元三次方程求解

视频讲解可以直接点击这个 B 站链接，https://www.bilibili.com/video/BV1qT4y13717/。

题目相关

题目链接

洛谷，https://www.luogu.com.cn/problem/P1024。

我的 OJ，http://47.110.135.197/problem.php?id=4242。

题目描述

有形如： 这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d 为实数），并约定该方程存在三个不同实根（根的范围在 -100 − 100 之间），且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后 2 位。

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

输入格式

一行，4 个实数 A，B，C，D。

输出格式

一行，3 个实根，并精确到小数点后 2 位。

输入样例

1 -5 -4 20

输出样例

-2.00 2.00 5.00

题目分析

题意分析

给了一个特殊的一元三次方程，该方程在 [-100, 100] 之间存在 3 个不同的实根，而且实根之间差的绝对值大于等于 1。要求我们求出这 3 个实根。

样例数据分析

本题是一个方程求解问题，样例数据没什么需要分析的，跳过。

数据规模分析

[-100, 100] 之间求解，而且要求的精度为小数点后 2 位，也就是 1e-2。

这句话意味着什么？

，看懂没有？

算法思路

从上面的数据规模分析可以得出，最大的数据个数就是 20,000 个中筛选出 3 个数据。数据量小得可怜。因此本题的解法有很多种。

枚举算法

所谓暴力出奇迹。我们可以看到，要求精度是 0.01，数据范围为 [-100, 100]，在这个范围一共有 20,000 个数据，完全可以考虑用暴力枚举。

也就是从 -100 开始，到 100 结束，每间隔 0.01，对数据进行枚举。

AC 参考代码

#include <bits/stdc++.h>

const double EPS = 1e-6;

int main() {
    double a,b,c,d;
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

    //枚举算法
    for (double i=-100; i<=100; i+=0.01) {
        double ans = a*i*i*i+b*i*i+c*i+d;
        if (fabs(ans)<EPS) {
            printf("%.2lf ", (double)i);
        }
    }
    printf("\n");

    return 0;
}

二分查找

本题和标准二分查找有些不一样。我们知道标准二分查找都是在某个范围内，查找一个数据。而本题是在 -100 到 100 之间，要求查找出所有答案。

因此为了套用标准浮点数二分查找，我们需要将 [-100, 100] 这个区间进行细分，然后在这个分区间里进行二分查找。因此本题的核心就是如何找到有解的区间，然后在这个区间进行二分。

查找有解区间

其实题目已经告诉我们如何查找。关注以下几个部分：

1、根与根之差的绝对值 ≥ 1。

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

浮点二分的难点

就是 check() 函数如何写。

本题 check() 函数还是需要参考“记方程 f(x) = 0，若存在 2 个数 x1 ​和 x2​，且 x1 ​< x2​，f(x1​)×f(x2​) < 0，则在 (x1​, x2​) 之间一定有一个根”这句话。

AC 参考代码

直接套用浮点数二分查找模板代码即可。

#include <bits/stdc++.h>

double a,b,c,d;
const double EPS = 1e-4;

double calc(double mid) {
    return a*mid*mid*mid+b*mid*mid+c*mid+d;
}

bool check(double left, double mid) {
    double x1 = calc(left);
    double x2 = calc(mid);
    return x1*x2<0 ? true : false;
}

double bsearch(double left, double right) {
    double mid;
    while (fabs(right-left)>EPS) {
        mid = (left+right)/2;

        if (check(left, mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    return left;
}

int main() {
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

    for (int i=-100; i<=100; i++) {
        double x1 = calc(i);
        double x2 = calc(i+1-EPS);

        if (fabs(x1)<EPS) {
            printf("%.2lf ", (double)i);
        } else if (x1*x2<0) {
            printf("%.2lf ", bsearch(i, i+1));
        }
    }
    printf("\n");

    return 0;
}

代码细节

1、EPS 定义。根据经验公式，只需要比题目要求精度大两个数量级即可。因此 1e-4 对于本题而言，足够了。

2、check() 函数。我们知道该函数的作用是缩小查找的范围，本来我们是在 [left, right] 这个范围找答案。因此根据题目提供的有根条件，我们可以尝试在 [left, mid] 这个范围查找是否存在根，然后根据反馈进行范围调整。当然也可以在 [mid, right] 这个范围查找。

3、由于根与根之差的绝对值 ≥ 1，这样查找区间总长不能为 2。如果查找的区间总长为 2，依据上面的代码，输入的数据为 1 -4.65 2.25 1.4。当 i=0 的时候，x1!=0 && x1*x2<0，我们用二分查找区间 [0, 1]之间可以查找到一个根为 1.00。当 i=1 的时候，x1=0，又会输出一个根 1.00。导致出现重复答案。