[NOIP2001-提高] 一元三次方程求解

题目描述

给定一元三次方程 $ax^3+bx^2+cx+d=0$ 的四个实数系数 $a,b,c,d$ ，约定方程存在三个不同实根，根都在 $[-100,100]$ 内，且任意两根之差的绝对值 $\ge 1$ 。求由小到大在同一行输出这三个实根，精确到小数点后 2 位，根之间用空格隔开。 输入格式：一行 4 个实数 $A,B,C,D$ 。输出格式：一行 3 个实根，精确到小数点后 2 位。 输入样例：1 -5 -4 20；输出样例：-2.00 2.00 5.00

思路

利用提示中的介值定理： $f$ 连续，若 $f(x_1)\times f(x_2)<0$ 则两点之间必有根。在 $[-100,100]$ 上每 $0.5$ 取一个采样点（ $400$ 个相邻区间），因为两根之差 $\ge 1$ ，每个小区间内至多一个根，发现相邻采样点函数值变号就对这个小区间二分求根即可。

参考代码

Python 版：

python

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:18
# update_at: 2026-10-02 04:18

import sys

# 判定精度的绝对/相对容差：|f| <= tol 视为零点附近
TOL = 1e-6


def eval_poly(c: list[float], x: float) -> float:
    """秦九韶算法求三次多项式 c[0]*x^3+c[1]*x^2+c[2]*x+c[3] 在 x 处的值。"""
    y = 0.0
    for coef in c:
        y = y * x + coef
    return y


def bisect(c: list[float], lo: float, hi: float) -> float:
    """已知 f(lo)*f(hi)<0，对 [lo,hi] 二分 80 次得到足够精确的根。"""
    flo = eval_poly(c, lo)
    for _ in range(80):
        mid = (lo + hi) / 2
        if eval_poly(c, mid) * flo < 0:
            hi = mid
        else:
            lo = mid
    return (lo + hi) / 2


def shrink(c: list[float], x: float) -> float:
    """重根收缩：重根处 f 不变号，二分失效；
    但重根必是导数的零点（驻点），取离 x 最近的驻点候选并验证。"""
    # 采样零点/二分结果本身已足够精确，直接采用
    if abs(eval_poly(c, x)) <= TOL:
        return x
    # 解 f'(x)=3c0x^2+2c1x+c2=0 的两个驻点，取离 x 最近者为重根候选
    c0, c1, c2 = c
    a, b, cc = 3 * c0, 2 * c1, c2
    disc = b * b - 4 * a * cc
    if disc < 0:
        return x
    r = disc**0.5
    cand = min(((-b + r) / (2 * a), (-b - r) / (2 * a)), key=lambda t: abs(t - x))
    # 候选处 |f| 足够小才采纳，防止把普通驻点误认为根
    return cand if abs(eval_poly(c, cand)) <= TOL else x


def roots(c: list[float]) -> list[float]:
    """在 [-100,100] 上从小到大找出全部实根（含重根），间隔 >= 1。"""
    step = 0.5
    xs = [-100.0 + i * step for i in range(401)]  # 401 个采样点
    vals = [eval_poly(c, x) for x in xs]
    ans: list[float] = []
    last = None  # 上一个已输出的根，用于去重重根
    # 逐区间检查变号：f 符号翻转 => 区间内恰有一根（间隔>=1保证唯一）
    for i in range(400):
        if vals[i] == 0.0:
            r = xs[i]
        elif vals[i] * vals[i + 1] < 0:
            r = bisect(c, xs[i], xs[i + 1])
        else:
            continue
        r = shrink(c, r)  # 端点根可能是重根，收缩到真正的重根位置
        if last is None or abs(r - last) >= 0.5:
            ans.append(r)
            last = r
    return ans


def solve() -> None:
    data = iter(map(float, sys.stdin.buffer.read().split()))
    a, b, c, d = next(data), next(data), next(data), next(data)
    print(" ".join(f"{r:.2f}" for r in roots([a, b, c, d])))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 12:33
 * update_at: 2026-10-06 12:33
 */

#include <cstdio>

typedef long long ll;

// f(x) = a*x^3 + b*x^2 + c*x + d
double A, B, C, D;

// 计算多项式在 x 处的值（秦九韶）
double calc(double x) {
    return ((A * x + B) * x + C) * x + D;
}

int main() {
    scanf("%lf %lf %lf %lf", &A, &B, &C, &D);
    double last = 0;
    bool has_last = false; // 是否已经找到过一个根，用于间隔去重
    // 在 [-100,100] 上每 0.5 采样一次，两根之差 >= 1 保证每个小区间内至多一个根
    for (double x = -100.0; x < 100.0; x += 0.5) {
        double y1 = calc(x), y2 = calc(x + 0.5);
        if (y1 * y2 > 0) continue; // 同号，此区间无根
        // 二分变号区间 [x, x+0.5]，迭代足够多次把根逼到两位小数精度内
        double l = x, r = x + 0.5;
        for (int i = 1; i <= 100; ++i) {
            double mid = (l + r) / 2;
            if (calc(l) * calc(mid) <= 0)
                r = mid;
            else
                l = mid;
        }
        double root = (l + r) / 2;
        // 根间距 >= 1，与上一个根距离过近说明是同一个根，不重复输出
        if (has_last && root - last < 0.5) continue;
        printf("%.2f ", root);
        last = root;
        has_last = true;
    }
    printf("\n");
    return 0;
}

[NOIP2001-提高] 一元三次方程求解

目录

题目描述

思路

参考代码