洛谷 P1024 — 一元三次方程求解

题目描述

有形如：ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值> =1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
　　提示：记方程f(x)=0，若存在2个数x1和x2，且x1< x2，f(x1)*(x2)< 0，则在(x1，x2)之间一定有一个根。

题目链接

https://www.luogu.org/problem/P1024

输入数据

输入该方程中各项的系数 (a ， b ， c ， d 均为实数)，

输出数据

由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。

样例输入

1 -5 -4 20

样例输出

-2.00 2.00 5.00

题目分析

根的范围是-100至100，所以从左到右枚举，找到第一个 right 使得 f(-100) * f(right) < 0 ，然后在 -100 到 right 之间进行二分查找，寻找根的值。同理在找出另外两个区间，进行二分即可。
寻找区间时，每次枚举的大小只要小于1即可，因为根与根之差的绝对值>=1

AC代码

#include <bits/stdc++.h>
using namespace std;

double a, b, c, d;

double f(double x)
{
    return a * x * x * x + b * x * x + c * x + d;
}

double GetRight(double left)
{
    for (double i = left; i <= 100; i += 0.9)
    {
        if (f(left) * f(i) < 0)
        {
            return i;
        }
    }
    return -999; //没有找到
}

int main()
{
    double left, right, left2, right2, mid;
    int t = 0; //解的个数
    cin >> a >> b >> c >> d;
    left = -100;
    right = GetRight(left);
    left2 = left, right2 = right;
    while (left2 <= right2)
    {
        mid = (left2 + right2) / 2;
        if (fabs(f(mid)) < 0.00001)
        {
            t++;
            if (t > 1)
                printf(" ");
            printf("%.2f", mid);
            left = right;
            if (t == 3)
                break;
            right = GetRight(left);
            left2 = left, right2 = right;
            continue;
        }
        if (f(mid) * f(left2) > 0)
            left2 = mid;
        else
            right2 = mid;
    }
    return 0;
}