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

题目描述

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

提示：记方程 $f(x)=0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，则在 $(x_1,x_2)$ 之间一定有一个根。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1 -5 -4 20

样例输出 #1

-2.00 2.00 5.00

提示

【题目来源】

NOIP 2001 提高组第一题

代码

  程序使用了二分查找法来精确查找方程的实根。首先，它枚举了-100到100之间的所有整数i，作为可能根的起始值。如果f(i)为0或者f(i)与f(i+1)的乘积为负数（这意味着i和i+1之间有一个根），则使用二分法在该区间内搜索具体的根，直至区间长度小于1e-6。每找到一个根，就打印出来，并且保持根的计数。当找到三个根后，程序终止。

// 引入头文件
#include<bits/stdc++.h>
// 引入std命名空间，避免每次调用标准库函数时都要加上std::前缀
using namespace std;// 定义全局变量存储方程的系数
double a, b, c, d;// 定义函数f，计算方程ax^3 + bx^2 + cx + d的值
double f(double x)
{return a*x*x*x + b*x*x + c*x + d;
} // 主函数
int main()
{// 输入方程的系数cin >> a >> b >> c >> d;// i为循环变量，用于枚举可能的根double i;// count用于计数找到的根int count = 0;// 枚举-100至100之间的所有整数for(i = -100; i < 100; i++){// 如果f(i)等于0，i是方程的根if(f(i) == 0){// 计数加一count++;// 输出根，并保留两位小数printf("%.2f ", i);continue;}// 如果f(i)与f(i+1)的乘积小于0，说明在i和i+1之间存在根if(f(i) * f(i+1) < 0){// 计数加一count++;// l和r分别为二分法的左右端点，初始时为i和i+1double l = i, r = i + 1;// 当l和r之间的距离大于1e-6时，进行二分查找while(r - l > 1e-6){// mid为l和r的中点double mid = (r + l) / 2.0;// 如果f(mid)与f(l)的乘积小于0，说明根在l和mid之间if(f(mid) * f(l) < 0)r = mid;else // 否则，根在mid和r之间l = mid;}// 输出找到的根，并保留两位小数printf("%.2f ", l);}// 如果找到了三个根，退出循环if(count == 3) break;}// 结束程序return 0;
}