P1024 一元三次方程求解(分治算法)

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

提示:记方程f(x)=0,若存在2个数x1​和x2​,且x1​<x2​,f(x1​)×f(x2​)<0,则在(x1​,x2​)之间一定有一个根。

输入格式:一行,4个实数A,B,C,D

输出格式:一行,3个实根,并精确到小数点后2位。

题目的数据范围不大,且根与根的绝对值之差大于等于1,因此可以考虑枚举宽度为1的区间。只要这个区间的左端点和右端点的函数值乘积小于零(即两个函数值异号),则其中必定有一个根。然后可以使用二分算法,即每次取区间中点,如果中点和左端点的函数值乘积小于零,则在(左端点,中点)间一定有一个根。再将中点赋值为右端点,继续上述操作。否则,在(中点,右端点)间有根,将中点赋值为左端点,继续上述操作。直到左端点和右端点的差小于0.001(题目要求精确到小数点后2位),此时输出任意一个端点。这里使用右端点。注意:如果在枚举区间时,左端点的函数值恰好等于0,则直接输出,不需再二分。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
double a,b,c,d;
double func(int x)
{
    return a*x*x*x+b*x*x+c*x+d;//求函数值
}
int main()
{
    double left,right,mid;
    int p=0;
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);//输入系数
    for(double i=-100.00;i<=100.00;i+=1.00)
    {
        double j=i+1.00;//枚举区间
        if(func(i)==0.00) //左端点就是一个解
        {
            printf("%.2lf ",(double)i);
            p++;
        }
        if(func((double)i)*func((double)j)<0)//发现区间(left,right)中有解
        {
            left=i;right=j;
            while(right-left>=0.001)//二分
            {
                mid=(left+right)/2;//取中间值
                if(func(mid)*func(left)<0)//判定解的区域为(left,mid)
                {
                    right=mid;
                }
                else//判定解的区域为(mid,right)
                {
                    left=mid;
                }
            }
            printf("%.2lf ",right);
            p++;
        }
        if(p==3) break;//一元三次方程至多有三个解
    }
    return 0;
}

 

 
上一篇:IOS中陀螺仪的使用方法


下一篇:phpstorm设置换行兼容Windows(CRLF)和Linux(LF)