【NOIP提高组】一元三次方程求解

💐The Begin💐点点关注，收藏不迷路💐

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。

输入
输入该方程中各项的系数(a，b，c，d均为实数)

输出

由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位

样例输入

1 -5 -4 20

样例输出

-2.00 2.00 5.00

1、C语言实现：

#include <stdio.h>
#include <math.h>

// 定义函数 equation，用于计算给定 x 和系数 a、b、c、d 的方程值
double equation(double x, double a, double b, double c, double d) {
    return a * x * x * x + b * x * x + c * x + d;
}

int main() {
    double a, b, c, d;
    // 从用户输入读取方程的系数 a、b、c、d
    scanf("%lf %lf %lf %lf", &a, &b, &c, &d);

    for (double i = -100; i <= 100; i += 0.01) {
        double j = i + 0.01;
        // 计算 i 处的方程值
        double value_i = equation(i, a, b, c, d);
        // 计算 j 处的方程值
        double value_j = equation(j, a, b, c, d);
        if (value_i * value_j < 0) {
            // 如果 i 和 j 处的方程值乘积小于 0，说明在区间 (i,j) 中有根
            double left = i;
            double right = j;
            while (right - left > 0.0001) {
                // 计算区间的中点
                double mid = (left + right) / 2;
                // 计算中点处的方程值
                double mid_value = equation(mid, a, b, c, d);
                if (mid_value * value_i < 0) {
                    // 如果中点值和 i 处值的乘积小于 0，说明根在区间 (left,mid)
                    right = mid;
                } else {
                    // 否则根在区间 (mid,right)
                    left = mid;
                }
            }
            // 输出找到的根，精确到小数点后两位
            printf("%.2lf ", left);
        }
    }
    return 0;
}

在这里插入图片描述

以下是对上述 C 语言代码求解一元三次方程的解法解析：

一、问题分析

已知条件
- 有形如 $ax^3 + bx^2 + cx + d = 0$ 的一元三次方程。
- 方程存在三个不同实根，且根的范围在 -100 至 100 之间，根与根之差的绝对值大于等于 1。
- 若存在两个数 $x_1$ 和 $x_2$ ，且 $x_1\lt x_2$ ， $f(x_1)\times f(x_2)\lt0$ ，则在 $x_1,x_2)$ 之间一定有一个根。
求解目标
- 求出满足条件的三个实根，并从小到大依次输出，精确到小数点后两位。

二、算法思路

遍历区间
- 从 -100 开始，以 0.01 为步长遍历到 100。对于每个值 $i$ ，计算方程在该点的值 $value\_i$ 。
- 同时计算下一个点 $j = i + 0.01$ 处的方程值 $value\_j$ 。
确定根的区间
- 如果 $value\_i\times value\_j\lt0$ ，说明在区间 $(i, j)$ 之间必然存在一个根。
二分法逼近根
- 定义区间的左右边界 $l e f t = i$ 和 $r i g h t = j$ 。
- 不断进行二分查找，直到区间长度小于一个很小的阈值（这里是 0.0001）。
- 在每次迭代中，计算区间的中点 $mi d = (l e f t + r i g h t) /2$ 以及中点处的方程值 $mid\_value$ 。
- 如果 $mid\_value\times value\_i\lt0$ ，说明根在区间 $(l e f t, mi d)$ ，更新右边界 $r i g h t = mi d$ ；否则根在区间 $(mi d, r i g h t)$ ，更新左边界 $l e f t = mi d$ 。
输出结果
- 当找到一个根后，输出该根，精确到小数点后两位。
- 继续遍历区间，寻找另外两个根。

三、代码解释

equation 函数
- 该函数用于计算给定 $x$ 值下方程的值。
- 接收系数 $a$ 、 $b$ 、 $c$ 、 $d$ 和变量 $x$ ，返回 $ax^3 + bx^2 + cx + d$ 的值。
main 函数
- 首先读取输入的方程系数 $a$ 、 $b$ 、 $c$ 、 $d$ 。
- 然后通过循环遍历 -100 到 100 的区间，步长为 0.01。
- 对于每个点，计算其方程值，并与下一个点的方程值进行比较，确定根的区间。
- 一旦确定根的区间，使用二分法逼近根，并输出结果。

四、时间复杂度和空间复杂度分析

时间复杂度
- 主要的时间消耗在遍历区间和二分法查找上。遍历区间的时间复杂度为 $O (20000)$ （因为从 -100 到 100，步长为 0.01，共 20000 个点）。
- 对于每个可能的根区间，二分法查找的时间复杂度为 $O (l o g (0.01/ s t e p))$ ，其中 $s t e p$ 是遍历区间的步长。
- 总体时间复杂度近似为 $O(20000\times log(0.01/0.01)) = O(20000)$ 。
空间复杂度
- 代码中只使用了有限的几个变量，空间复杂度为 $O (1)$ 。

2、JAVA实现：

import java.util.Scanner;

class Main {
    // 定义一个静态方法，用于计算方程的值
    public static double equation(double x, double a, double b, double c, double d) {
        return a * x * x * x + b * x * x + c * x + d;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入的方程系数 a、b、c、d
        double a = scanner.nextDouble();
        double b = scanner.nextDouble();
        double c = scanner.nextDouble();
        double d = scanner.nextDouble();

        for (double i = -100; i <= 100; i += 0.01) {
            // 定义 j 为下一个步长的值
            double j = i + 0.01;
            // 计算 i 处的方程值
            double value_i = equation(i, a, b, c, d);
            // 计算 j 处的方程值
            double value_j = equation(j, a, b, c, d);
            if (value_i * value_j < 0) {
                // 如果 i 和 j 处的方程值乘积小于 0，说明在区间 (i,j) 中有根
                double left = i;
                double right = j;
                // 使用二分法逼近根
                while (right - left > 0.0001) {
                    double mid = (left + right) / 2;
                    double midValue = equation(mid, a, b, c, d);
                    if (midValue * value_i < 0) {
                        // 如果中点值和 i 处值的乘积小于 0，说明根在区间 (left,mid)
                        right = mid;
                    } else {
                        // 否则根在区间 (mid,right)
                        left = mid;
                    }
                }
                // 输出找到的根，精确到小数点后两位
                System.out.printf("%.2f ", left);
            }
        }
    }
}