【NOIP】2001真题解析 luogu-P1024 一元三次方程求解
NOIP 2001真题，二分法考点应用，重点理解二分思想应用。GESP 五、六级考生可以练习。题目难度⭐⭐★☆☆，洛谷难度等级普及−。
luogu-P1024 [NOIP 2001 提高组] 一元三次方程求解
题目要求
题目描述
有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。
输入格式
一行，$4$ 个实数 $a, b, c, d$。
输出格式
一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。
输入输出样例 #1
输入 #1
1
2
1 -5 -4 20
输出 #1
1
2
-2.00 2.00 5.00
说明/提示
【题目来源】
NOIP 2001 提高组第一题
题目分析
1. 核心思路：分治与二分 (Divide and Conquer & Binary Search)
这道题的核心难点在于如何在一个较大的范围（-100 到 100）内找到三个精确的实数根。直接对整个区间进行二分查找行不通，因为函数不是单调的（三次函数图像呈“N”字形或反“N”字形）。
解题策略：区间枚举 + 二分查找
由于题目给出了两个关键信息：
- 根的范围：在 $-100$ 到 $100$ 之间。
- 根的间距：根与根之差的绝对值 $\ge 1$。
这两个条件暗示我们可以将大区间 $[-100, 100]$ 切分为若干个长度为 1 的小区间（即 $[-100, -99], [-99, -98], \dots, [99, 100]$）。 在每个长度为 1 的小区间 $[i, i+1]$ 内，利用零点存在性定理（即题目中的提示方法）判断是否存在根。
2. 算法流程
枚举区间：从 $i = -100$ 遍历到 $i = 99$。对于每一个整数 $i$，我们考察区间 $[i, i+1]$。
- 判断根的存在性：
- 情况 A：左端点是根。 计算 $f(i)$。如果 $f(i) == 0$，说明 $i$ 就是一个整数根，直接输出。
- 情况 B：区间内有根。 计算 $f(i)$ 和 $f(i+1)$。如果 $f(i) \times f(i+1) < 0$，根据连续函数的零点存在性定理，在开区间 $(i, i+1)$ 内必然存在一个根。此时，在这个小区间内进行二分查找。
- 情况 C：忽略右端点。 通常我们不在当前区间处理右端点 $i+1$ 为根的情况（即 $f(i+1) == 0$），因为 $i+1$ 会作为下一个区间的左端点被处理。这样可以避免重复输出同一个根。
- 二分查找 (Binary Search)：当确定区间 $[x_1, x_2]$ 内有根时，使用二分法逼近：
- 设定左边界 $l = x_1$，右边界 $r = x_2$。
- 取中点 $mid = l + (r-l) / 2$。
- 判断根在左半段还是右半段：如果 $f(l) \cdot f(mid) \le 0$，则根在 $[l, mid]$，令 $r = mid$；否则根在 $[mid, r]$，令 $l = mid$。
- 精度控制：循环固定次数（如 100 次），或当 $r - l < \epsilon$ 时停止。本题代码采用循环 100 次的方法，简单且能保证极高的精度（$1/2^{100}$ 极其微小）。
3. 核心要点总结
- 区间长度的选择：为什么选长度为 1？因为题目保证根的间距 $\ge 1$。这意味着在一个长度为 1 的区间 $(i, i+1)$ 内，不可能存在两个或以上的根。这保证了我们在该区间内使用二分查找时，不会漏掉根，也不会因为非单调性导致错误（在单根区间内，三次函数也是单调的）。
- 端点处理：必须精确处理端点等于 0 的情况。代码中优先判断
if (f1 == 0)，输出确切的整数根；然后再用else if (f1 * f2 < 0)寻找非整数根。 - 精度技巧：二分查找时，直接
for (int k = 0; k < 100; k++)是一种非常实用的竞赛技巧。相比于while (r - l > 1e-4)，它避免了死循环的风险，且对于double类型来说，100 次二分已经达到了精度的极限。 - 零点定理的应用：
f(x1) * f(x2) < 0是判断连续函数在区间内是否有零点的金标准。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <iostream>
double a, b, c, d;
// 计算方程 f(x) 的值
double f(double x) { return a * x * x * x + b * x * x + c * x + d; }
int main() {
// 禁用 I/O 同步，提高输入输出效率
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// 读取输入的系数 a, b, c, d
std::scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
// 在 [-100, 100] 范围内枚举每一个长度为 1 的区间
for (int i = -100; i < 100; i++) {
double x1 = i; // 区间左端点
double x2 = i + 1; // 区间右端点
double f1 = f(x1); // 左端点函数值
double f2 = f(x2); // 右端点函数值
// 如果左端点 x1 是根
if (f1 == 0) {
std::printf("%.2lf ", x1);
}
// 如果区间 (x1, x2) 内有根 (根据零点存在定理：f(x1) * f(x2) < 0)
// 注意：如果 f(x1) == 0，这一步会跳过，避免重复输出
// 如果 f(x2) == 0，这一步也会跳过，留给下一次循环的 f(x1) 处理
else if (f1 * f2 < 0) {
// 二分查找
double l = x1;
double r = x2;
// 精度控制：直接循环固定次数（如 100 次）是一种常用且安全的技巧
// 循环 100 次后，区间长度会缩小到 1/2^100，精度极高且不会死循环
double ans = l;
for (int k = 0; k < 100; k++) {
double mid = l + (r - l) / 2; // 计算中点
// 如果 f(l) 和 f(mid) 异号，说明根在左半区间 [l, mid]
if (f(l) * f(mid) <= 0) {
r = mid;
} else {
// 否则根在右半区间 [mid, r]
l = mid;
}
}
// 输出找到的根，保留两位小数
std::printf("%.2lf ", r);
}
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
