【洛谷】P1024 [NOIP2001 提高组] 一元三次方程求解 （二分）

题目描述见此：P1024

如何求一个方程的根呢qwq

首先，根是什么，函数y＝f(x)有零点 ⇔ 方程f(x)＝0有实数根 ⇔ 函数y＝f(x)的图象与x轴有交点。回顾我们高一学过的一个定理：

零点存在性定理：

如果函数y＝f(x)在区间[a, b]上的图象是连续不断的一条曲线，并且有f(a)·f(b)＜0，那么，函数y＝f(x)在区间(a, b)内有零点，即存在c∈(a, b)，使得f(c)＝0，这个c也就是方程f(x)＝0的根。

首先题目只要求我们求区间 [-100,100] 的根，若要利用零点存在性求出方程的根，我们可以先从i（i=-100）开始，先把区间分成 [i,i+1]在这个区间利用零点存在性定理判断是否存在零点，若存在就进行二分，不存在就一直迭代到存在的区间为止。

一开始考虑到函数的模样，还在想如何确定最开始的区间呢www计算机还是强大的诶，没想到直接从头到尾过一遍就好了233333

在这里复习一下浮点数二分的板子qwq

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double binarySearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

接下来就是题解啦！

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

#define eps 1e-4 //精度
double A, B, C, D;

double f(double x) {
	return (A * x * x * x + B * x * x + C * x + D);
} //函数定义

int main() {
	cin >> A >> B >> C >> D;
	for (int i = -100; i <= 100; i++) {
		double l = i, r = i + 1, mid;
		if (fabs(f(l)) < eps)
			printf("%.2lf ", l);     //若左侧是根，直接输出
		else if (fabs(f(r)) < eps)   //若右侧是根，跳过循环，因为如果输出，下一轮循环也会重复输出同一答案
			continue;

		else if (f(l)*f(r) < 0) {   //若存在零点开始二分
			while (r - l > eps) {
				mid = (l + r) / 2;
				if (f(mid)*f(r) > 0)   //零点不在 [mid,r] 内，那么r往左边走
					r = mid;
				else
					l = mid;。   //否则就继续二分缩小区间
			}
			printf("%.2lf ", l);
		}
	}
	return 0;
}