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

题目描述

有形如：$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$ 这就是突破口 这说明在每一个大小为1的区间最多有一个解 也就是说假设x~x+1这个长度为1的区间存在解 那么只会有一个解 我们可以以x和x+1作为端点 对这个区间内存在的一个解进行二分求出
我们把$[-100, 100]$这个区间划分为一个一个长度为1的小区间 判断里面有没有解就可以算出所有的解
那怎么判断某一个长度为1的区间有没有解呢
高中知识：$f(x_1) \times f(x_2) < 0$ 当区间端点函数值不同 证明函数穿过了x轴就会存在一个解
我们从-100开始枚举互相不重叠的每一个长度为1的区间，在区间内进行二分查找。
上代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n';

double a, b, c, d; 

double fy(double x) //返回当前点x的函数值 
{
    return a * x * x * x + b * x * x + c * x + d;
}

void solve()
{
    cin >> a >> b >> c >> d;
    for (int i = -100; i <= 100; i ++ )
    {
        //定义左右端点 区间长度为1 
        double x1 = i;
        double x2 = i + 1;

        if (fy(x1) == 0) cout << fixed << setprecision(2) << x1 << " "; //记录端点会不会就是一个解 注意 这里只用判断左端点 下次循环左端点右移1位就是现在的右端点 所以只判断一次 否则会重复计算 
        if (fy(x1) * fy(x2) < 0)
        {
            double l = x1, r = x2;
            while (r - l >= 1e-4) //浮点数二分模板 这里要写成r - l 刚开始写反了 l - r就成负数了 
            {
                double mid = (l + r) / 2;
                if (fy(mid) * fy(r) <= 0) l = mid; //这里刚开始写错了 写成 fy(l) * fy(r) 了 这样就用不到mid了 应该是将mid作为端点 与r作为端点 判断他们其中有没有解 有解就将l赋值为mid 开始下一次二分 
                else r = mid;
            }
            cout << fixed << setprecision(2) << l << " "; 
        }
    }
    cout << endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}