【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 语言代码求解一元三次方程的解法解析：

一、问题分析

1. 已知条件

   • 有形如 $a{x}^3+b{x}^2+cx+d=0$ 的一元三次方程。
   • 方程存在三个不同实根，且根的范围在 -100 至 100 之间，根与根之差的绝对值大于等于 1。
   • 若存在两个数 $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，则在 $(x_1,x_2)$ 之间一定有一个根。

2. 求解目标

   • 求出满足条件的三个实根，并从小到大依次输出，精确到小数点后两位。

二、算法思路

1. 遍历区间

   • 从 -100 开始，以 0.01 为步长遍历到 100。对于每个值 $i$，计算方程在该点的值 $value\_i$。
   • 同时计算下一个点 $j=i+0.01$ 处的方程值 $value\_j$。

2. 确定根的区间

   • 如果 $value\_i\times value\_j<0$，说明在区间 $(i,j)$ 之间必然存在一个根。

3. 二分法逼近根

   • 定义区间的左右边界 $left=i$ 和 $right=j$。
   • 不断进行二分查找，直到区间长度小于一个很小的阈值（这里是 0.0001）。
   • 在每次迭代中，计算区间的中点 $mid=(left+right)/2$ 以及中点处的方程值 $mid\_value$。
   • 如果 $mid\_value\times value\_i<0$，说明根在区间 $(left,mid)$，更新右边界 $right=mid$；否则根在区间 $(mid,right)$，更新左边界 $left=mid$。

4. 输出结果

   • 当找到一个根后，输出该根，精确到小数点后两位。
   • 继续遍历区间，寻找另外两个根。

三、代码解释

1. equation 函数

   • 该函数用于计算给定 $x$ 值下方程的值。
   • 接收系数 $a$、$b$、$c$、$d$ 和变量 $x$，返回 $a{x}^3+b{x}^2+cx+d$ 的值。

2. main 函数

   • 首先读取输入的方程系数 $a$、$b$、$c$、$d$。
   • 然后通过循环遍历 -100 到 100 的区间，步长为 0.01。
   • 对于每个点，计算其方程值，并与下一个点的方程值进行比较，确定根的区间。
   • 一旦确定根的区间，使用二分法逼近根，并输出结果。

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

1. 时间复杂度

   • 主要的时间消耗在遍历区间和二分法查找上。遍历区间的时间复杂度为 $O(20000)$（因为从 -100 到 100，步长为 0.01，共 20000 个点）。
   • 对于每个可能的根区间，二分法查找的时间复杂度为 $O(log(0.01/step))$，其中 $step$ 是遍历区间的步长。
   • 总体时间复杂度近似为 $O(20000\times log(0.01/0.01))=O(20000)$。

2. 空间复杂度

   • 代码中只使用了有限的几个变量，空间复杂度为 $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);
            }
        }
    }
}

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

原文地址：https://blog.csdn.net/qq_41840843/article/details/143086344

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！