P1024. 一元三次方程求解

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 402 阅读时长 ≈ 1 分钟

考点

  • 二分
  • 分治

题解

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
#include <bits/stdc++.h>

using namespace std;

#define eps 1e-4

double A, B, C, D;

double f(double x)
{
    return A * pow(x, 3) + B * pow(x, 2) + C * x + D;
}

void print(double x)
{
    printf("%.2lf ", x);
}

int main()
{
    cin >> A >> B >> C >> D;
    double l, r, mid, a, b;
    for (double x = -100; x < 100; ++x)
    {
        l = x, r = x + 1, a = f(l), b = f(r);
        if (fabs(a) < eps)
            print(l);
        else if (fabs(b) < eps)
            continue;
        else if (a * b < 0)
        {
            while (r - l > eps)
            {
                mid = (l + r) / 2;
                if (a * f(mid) > 0)
                    l = mid;
                else
                    r = mid;
            }
            print(mid);
        }
    }
    return 0;
}

思路

二分应用的模板题

根在-100~100的范围内，且根与根之间的绝对值大于等于1；可以将整体拆分为若干个区间长度为1的子区间进行二分求解

那么二分的左端点l范围从-100到99，右端点r就比l多1即可

根据零值定理可知，在一个区间内进行二分

若左右两端同朝一个点无限逼近（即右端点r与左端点l之间的距离小于某精度）且过程中两端函数值均异号，该点就是零点

那么二分中的l，r与中点mid该如何变换呢？

如果中点的函数值和某端点的正负性相同，那么零点一定在中点的另一侧

当然，还有特殊情况：

  • 左端点就是零点，输出这个零点
  • 右端点就是零点，直接continue进行下一次（因为当前区间的右端点，就是下一轮区间的左端点）
  • 左右端点都是零点，该情况和左端点情况相同