P1024 一元三次方程求解
题目描述
有形如：ax3+bx2+cx1+dx0= 0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示
记方程f(x)=0，若存在2个数x1和x2，x1 < x2，x1 * x2 < 0，则在(x1，x2)且之间一定有一个根。
输入格式
一行，4个实数A,B,C,D。
输出格式
一行，3个实根，并精确到小数点后22位。
输入输出样例
输入 #1
1 -5 -4 20
输出 #1
-2.00 2.00 5.00
题目分析
通过二分找零点，因为数据范围非常小，而且跟与跟的绝对大于1，所以对每一个[l，l + 1] l ∈ [-100，100]进行二分搜索找零点，如何找零点在上面的提示中也有说明。
记方程f(x)=0，若存在2个数x1和x2，x1 < x2，x1 * x2 < 0，则在(x1，x2)且之间一定有一个根。可以结合上图来理解。
参考代码
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
double a, b, c, d;double f(double x) {return ((((a * x) + b) * x) + c) * x + d;
}int main() {// freopen("in.txt", "r", stdin);scanf("%lf%lf%lf%lf", &a, &b, &c, &d);int cnt = 0;for (double l = -100; l <= 100; l++) {double r = l + 1;// 然后在 [l,r] 之间找零点double fl = f(l), fr = f(r);if (fl * fr > 0) continue; // 同一个象限passif (!fl) {printf("%.2lf ", fl);cnt++;continue;}while (l < r - eps) {double mid = (l + r) / 2;if (f(mid) * f(l) <= 0) {r = mid; // 中点和左边端点是不同象限 说明零点在左边}else {l = mid;}}printf("%.2lf ", l);cnt++;if (cnt == 3) break;}return 0;
}
备注
注意实数二分需要有精度判断，在很多时候我们认为0.99999999和1是等价的。