一元三次方程（分治法）

目录

题目描述

分治法思想介绍

分治思路

我的代码

总结与展望

一元三次方程求解

【题目描述】

形如：这样的一个一元三次方程。

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

【输入】

一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。

【输出】

一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。

【输入样例】

1.0 -5.0 -4.0 20.0

【输出样例】

-2.00 2.00 5.00

一、分治法思想介绍

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题性质相同。求出子问题的解后，再合并这些子问题的解得到原问题的解。

分为如下三个步骤，俗称“分解合”：

（1）分解：将原问题分解为若干个规模较小的子问题，这些子问题相互独立，与原问题形式相同

（2）解决：若子问题规模较小而容易被解决则直接解，否则需要继续将子问题分解为更小的子问题，然后递归地解决这些子问题

（3）合并：将各个子问题的解合并为原问题的解

二、分治思路

形如： 的一元三次方程组

有如下性质：

              若 ，   那么一定会有 

确定根的区间：

枚举根的值域中每一个整数

由于根与根之差的绝对值≥1，因此设定搜索区间  ，

其中 L=i，R=i+1。若：

⑴     f(L)=0，则确定L为f(x)的根；

⑵     ，则确定根 x 不在区间内，设定 为下一个 搜索区间 ；

⑶     ，则确定根x在区间内。  

 分治思路:

已经确定根 x 在区间    内（），如何在该区间找到根的确切位置?

我们可以不断二分区间，直至找到答案。

取 L 与 R 的中点为 mid

如果  f(L)∗f(mid)<0 ， 则根 x 在（L , mid）区间内

同理  f(mid)∗f(R)<0 ，则根 x 在（mid , R）区间内

上述二分过程一直进行到区间的间距满足精度要求为止（）。此时确定 L 为f(x)的根。

三、我的代码

#include<iostream>
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;
}

//使用二分法查找根
void find(double l, double r)
{
	while (r - l > 0.001)
	{
		double mid = (l + r) / 2;
		if (f(l) * f(mid) <= 0) r = mid;
		else l = mid;
	}
	printf("%.2f ", l);
}

int main()
{
	int cnt = 0;//记录根的数量
	cin >> a >> b >> c >> d;

	//遍历从 -100 到 100 的范围，寻找方程组的根
	for (double i = -100; i <= 100, cnt != 3; i++)
	{
		if (f(i) == 0)
		{
			printf("%.2f ", i);
			cnt++;
			continue;
		}
		else if (f(i) * f(i + 1) < 0)
		{
			find(i, i + 1);
			cnt++;
		}
	}
	return 0;
}

四、总结与展望

题目来源：P1024 [NOIP2001 提高组] 一元三次方程求解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

算法分析：

时间复杂度：      可得  

代码的灵活性：修改cnt（根的数量），可以求解一元三次方程根的所有情况

                         修改循环条件，可以控制查找根的范围

                         修改区间间距，可以控制根的精度