题解：P1024 [NOIP2001 提高组] 一元三次方程求解#

题目描述#

给出一个形如 $ax^3 + bx^2 + cx + d = 0$ 的一元三次方程，系数均为实数。已知该方程在 $[-100, 100]$ 范围内存在三个不同的实根，且根与根之差的绝对值 $\ge 1$ 。要求从小到大输出这三个实根，精确到小数点后 2 位。

方法一：求导分区间法（我的解法）#

1. 算法思路#

一元三次函数 $f(x)$ 的图像通常呈“N”字形或倒“N”字形。为了找到三个根，我们需要确定函数的单调区间。单调性的转折点就是函数的极值点。

求导：对原函数求导得到二次函数 $f'(x) = 3ax^2 + 2bx + c$ 。
求极值点：令 $f'(x) = 0$ $f^{'} (x) = 0$ ，利用求根公式 $x = \frac{-B \pm \sqrt{B^2 - 4AC}}{2A}$ $x = \frac{- B \pm B ^{2} - 4 A C}{2 A}$ 求出两个极值点 $x_1, x_2$ $x_{1}, x_{2}$ 。
- 注意系数对应关系： $A=3a, B=2b, C=c$ 。
划分区间：两个极值点将数轴（在题目范围内）划分为三个单调区间：
- $[-100, x_1]$
- $[x_1, x_2]$
- $[x_2, 100]$
二分查找：由于题目保证有三个不同的实根，根据函数的连续性和单调性，这三个区间内必然各有一个根。我们只需要在每个区间内分别进行二分查找即可。

2. 代码实现#

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#include <iomanip>
5
#include <vector>
6

7
using namespace std;
8

9
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
10

11
typedef pair<double, double> PDD;
12

13
double a, b, c, d;
14

15
// 计算函数值 f(x)
16
double f(double x) {
17
    return a * x * x * x + b * x * x + c * x + d;
18
}
19

20
int main() {
21

22
    IOS;
23

24
    cin >> a >> b >> c >> d;
25

26
    // 1. 求导 f'(x) = 3ax^2 + 2bx + c
27
    double A = 3 * a;
28
    double B = 2 * b;
29
    double C = c;
30

31
    // 2. 求极值点（导数为0的点）
32
    double delta = B * B - 4 * A * C;
33
    double x1 = (-B + sqrt(delta)) / (2 * A);
34
    double x2 = (-B - sqrt(delta)) / (2 * A);
35

36
    // 确保 x1 < x2
37
    if (x1 > x2) swap(x1, x2);
38

39
    // 3. 划分三个单调区间
40
    vector<PII> sections(3);
41
    sections[0] = {-100, x1};
42
    sections[1] = {x1, x2};
43
    sections[2] = {x2, 100};
44

45
    // 4. 在每个区间内二分查找
46
    for (int i = 0; i < 3; i++) {
47
        double l = sections[i].first;
48
        double r = sections[i].second;
49

50
        // 当区间长度大于 1e-7 时继续二分，保证精度
51
        while (r - l > 1e-7) {
52
            double mid = (l + r) / 2;
53
            // 零点存在定理：如果 f(mid) 和 f(l) 异号（或其中之一为0），说明根在左半边
54
            // 注意：这里利用 f(l) 作为参考点判断符号变化
55
            if (f(mid) * f(l) <= 0) {
56
                r = mid;
57
            } else {
58
                l = mid;
59
            }
60
        }
61
        // 输出结果，控制精度
62
        cout << fixed << setprecision(2) << l << " ";
63
    }
64

65
    return 0;
66
}

3. 复杂度分析#

时间复杂度： $O(K)$ ，其中 $K$ 是二分的次数（常数）。
空间复杂度： $O(1)$ 。

方法二：暴力枚举 + 二分（答案推荐解法）#

1. 算法思路#

利用题目给出的强力提示：“根与根之差的绝对值 $\ge 1$ ”。这意味着，任意长度为 1 的区间 $[i, i+1]$ 内，最多只可能有一个根。

枚举：从 $-100$ 到 $99$ 枚举每一个整数 $i$ 。
判断：检查区间 $[i, i+1]$ $[i, i + 1]$ 的左右端点函数值。
- 如果 $f(i) = 0$ ，则 $i$ 是根。
- 如果 $f(i) \cdot f(i+1) < 0$ ，说明根在 $(i, i+1)$ 之间。
二分：对于确定的区间 $[i, i+1]$ ，进行二分查找精确求根。

2. 代码片段#

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#include <iomanip>
5
#include <vector>
6

7
using namespace std;
8

9
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
10

11
typedef pair<double, double> PDD;
12

13
double a, b, c, d;
14

15
// 计算函数值 f(x)
16
double f(double x) {
17
    return a * x * x * x + b * x * x + c * x + d;
18
}
19

20
int main() {
21

22
    IOS;
23

24
    cin >> a >> b >> c >> d;
25

26
    for (int i = -100; i < 100; i++) {
27
        double y1 = f(i);
28
        double y2 = f(i + 1);
29

30
        if (abs(y1) < 1e-9) { // 也就是 y1 == 0
31
            cout << fixed << setprecision(2) << (double)i << " ";
32
        }
33
        else if (y1 * y2 < 0) { // 区间内有根
34
            double l = i, r = i + 1;
35
            for (int k = 0; k < 100; k++) { // 二分 100 次
36
                double mid = (l + r) / 2;
37
                if (f(mid) * f(l) <= 0) r = mid;
38
                else l = mid;
39
            }
40
            cout << fixed << setprecision(2) << l << " ";
41
        }
42
    }
43

44
    return 0;
45
}