[NOIP2001 提高组] 一元三次方程求解（洛谷）

[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+1
            double 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;
}