一元三次方程求解(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 -5 -4 20

输出 #1

-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 是判断连续函数在区间内是否有零点的金标准。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月24日