问题 G: 一元三次方程求解

题目描述

有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值≥1。

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

提示：记方程f（x）=0，若存在2个数x1和x2，且x1<x2，f（x1）*f（x2）＜0，则在（x1，x2）之间一定有一个根。

输入

a，b，c，d

输出

三个实根（根与根之间留有空格）

样例输入

1 -5 -4 20

样例输出

2.00 2.00 5.00

问题分析

查找根的方法:

• 由于根之间的差至少为 1，可以通过检查相邻整数之间的区间来查找根。
• 对于每个这样的区间，可以使用二分查找方法来确定根的大致位置。

二分查找适用性:

• 二分查找是适用于这个问题的，因为如果 f(x1) 和 f(x2) 异号（即一个正一个负），则根据连续函数的中间值定理，存在一个 x 在 x1 和 x2 之间使得 f(x) = 0。

计算精度:

• 需要控制计算精度，确保找到的根足够接近真实值，并且在输出时有正确的小数位数。

程序实现:

• 程序需要遍历一个足够大的区间（在本例中为 -100 到 100），并在每个可能的子区间使用二分查找法来查找根。
• 输出时需要格式化数字，保留两位小数。

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

double a, b, c, d; // 定义方程的系数
// 定义函数 f，计算方程在 x 处的值
double f(double x) {
    return a * x * x * x + b * x * x + c * x + d;
}

int main() {
    cin >> a >> b >> c >> d; // 从标准输入读取方程的系数
    // 循环遍历-100到100之间的每个整数
    for (int i = -100; i <= 100; i++) {
        double l = i, r = i + 1, mid; // 设置搜索区间为 [i, i+1]
        // 检查左端点是否为根
        if (fabs(f(l)) < 1e-4) {
            printf("%.2lf ", l); // 如果是，则输出左端点
        }
            // 跳过右端点，因为它会在下一次迭代作为左端点被检查
        else if (fabs(f(r)) < 1e-4) {
            continue;
        }
            // 如果 f(l) 和 f(r) 异号，则说明区间 [l, r] 内存在根
        else if (f(l) * f(r) < 0) {
            // 使用二分法查找根
            while (r - l > 1e-4) { // 当区间宽度大于1e-4时继续查找
                mid = (r + l) / 2; // 计算区间中点
                // 如果 f(l) 和 f(mid) 同号，则根在区间 [mid, r]
                if (f(l) * f(mid) > 0)
                    l = mid;
                else // 否则根在区间 [l, mid]
                    r = mid;
            }
            printf("%.2lf ", l); // 输出找到的根
        }
    }
}