洛谷P1024[NOIP2001 提高组] 一元三次方程求解（cpp)(二分查找）

目录

1.题目

2.思路

3.AC

---

1.题目

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

## 题目描述

有形如： ?这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d?均为实数），并约定该方程存在三个不同实根（根的范围在 -100?至 100?之间），且根与根之差的绝对值 大于等于1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2?位。

提示：记方程 f(x) = 0，若存在 2个数 x1?和 x2，且 x1 < x2，f(x1) ×?f(x2) < 0，则在 (x1, x2)?之间一定有一个根。

## 输入格式

一行，4 个实数 a, b, c, d。

## 输出格式

一行，3 个实根，从小到大输出，并精确到小数点后 2?位。

## 样例 #1

### 样例输入 #1

```
1 -5 -4 20
```

### 样例输出 #1

```
-2.00 2.00 5.00
```

## 提示

**【题目来源】**

NOIP 2001 提高组第一题

2.思路

①a>0时，若??有三个实根，则图像为

图像与x轴的三个交点即为方程的三个根。将方程化为三个区间〔-100,t1〕,〔t1,t2〕,〔t2,100〕，利用二分查找就可以得到答案！

②如何得到t1,t2的值？对原方程求导，得到的导函数为，图像为

将方程化为两个区间〔-100,t0〕，〔t0,100〕，再利用二分查找！

③如何求t0？对函数再求导，使导函数为0，得t0 =?。

3.AC

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

int main () {
	double a, b, c, d, q[3];
	scanf("%lf%lf%lf%lf", &a, &b, &c, &d);

    //保证a>0
	if (a < 0) {
		a *= -1;
		b *= -1;
		c *= -1;
		d *= -1;
	}

    //求t0
	double t0 = -b/(3*a);

    //求t1
	double l = -100, r = t0;
	while (r - l > 1e-4) {
		double mid = (l+r)/2;
		if (3*a*mid*mid + 2*b*mid +c >= 0) l = mid;
		else r = mid;
	}
	double t1 = l;

	//求t2
	l = t0, r = 100;
	while (r - l > 1e-4) {
		double mid = (l+r)/2;
		if (3*a*mid*mid + 2*b*mid +c >= 0) r = mid;
		else l = mid;
	}
	double t2 = l;
	
    //求三个根
	l = -100, r = t1;
	while (r - l > 1e-4) {
		double mid = (l+r)/2;
		if (a*mid*mid*mid + b*mid*mid +c*mid + d >= 0) r = mid;
		else l = mid;
	}
	printf("%.2lf ", l);
	
	l = t1, r = t2;
	while (r - l > 1e-4) {
		double mid = (l+r)/2;
		if (a*mid*mid*mid + b*mid*mid +c*mid + d >= 0) l = mid;
		else r = mid;
	}
	printf("%.2lf ", l);
	
	l = t2, r = 100;
	while (r - l > 1e-4) {
		double mid = (l+r)/2;
		if (a*mid*mid*mid + b*mid*mid +c*mid + d >= 0) r = mid;
		else l = mid;
	}
	printf("%.2lf", l);

	return 0;
}