主要内容 #
- 问题描述
- 算法分析
- 参考程序
1. 问题描述 #
有形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。
给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。
提示:记方程f(x)=0,若存在两个数x1和x2,且x1 < x2,f(x1)*f(x2) < 0,则在(x1, x2)之间一定有至少一个根。
输入
一行,包含四个实数a,b,c,d,相邻两个数之间用单个空格隔开。
输出
一行,包含三个实数,为该方程的三个实根,按从小到大顺序排列,相邻两个数之间用单个空格隔开,精确到小数点后2位。
样例输入
1.0 -5.0 -4.0 20.0
样例输出
-2.00 2.00 5.00
2. 算法分析 #
这是一道有趣的解方程题。为了便于求解,设方程f(x)=ax^3+bx^2+cx+d=0,设根的范围(-100, 100)中有x,其左右两侧相距0.0005的地方有x1和x2两个数,即x1=x-0.0005,x1=x+0.0005。x1和x2之间的距离(0.001)满足精度要求(精确到小数点后2位)。如果f(x1)*f(x2)<=0,则可以确定x为f(x)=0的根。有两种方法可以计算。
2.1 枚举法 #
根据根的值域和根之间的间距要求(>=1),我们不妨将根的值域扩大100倍(-10000<=x<=10000),依次枚举该区域的每一个整数值x,并且在题目要求的精度内设置区间:x1=(x-0.05)/100,x1=(x+0.05)/100。若区间端点的函数值f(x1)和f(x2)异号或者在区间端点的函数值f(x1)=0,则确定(x/100)为f(x)=0的一个根。
由此得到此算法
//输入方程中各项的系数a, b, c, d。 for(x = -10000; x<=10000; x++){ //枚举当前根*100的可能范围 x1 = (x - 0.05)/100; x2 = (x + 0.05)/100; //若在区间两端的函数值异号或者在x1处的函数值为0,则确定x/100为根 if(f(x1) * f(x2) < 0 || f(x1) == 0){ printf("%2f", x/100); } } //其中函数f(x) = a*x*x*x+b*x*x+c*x+d。 double f(double){ return a*x*x*x+b*x*x+c*x+d; }
2.2 分治法 #
枚举根的值域中的每一个整数x(-100 <= x <= 100)。由于根与根之差的绝对值>=1,因此设定搜索区间[x1, x2],其中x1=x, x2=x+1。
- 若f(x1) = 0,则确定x1为f(x)的根;
- 若f(x1)*f(x2) > 0,则确定根不在区间[x1, x2]内,设定[x2, x2+1]为下一个搜索的区间;
- 若f(x1)*f(x2) < 0,则确定根在区间[x1, x2]内。
如果确定根x在区间[x1, x2]内的话(f(x1)*f(x2)<0),如何在该区间找到根的确切位置。采用二分法,将区间[x1, x2]分为左右两个子区间:左子区间[x1, x]和右子区间[x, x2],其中,x=(x1+x2)/2。
若f(x1)*f(x)<=0则确定根在左区间[x1, x]内,将x设为该区间的左指针(x2=x),继续对左子区间进行对分;若f(x1)*f(x)>0则确定根在左区间[x, x2]内,将x设为该区间的左指针(x1=x),继续对右子区间进行对分;
上述对分过程一直进行到区间距离满足精度要求为止(x2-x1<0.001)。此时,确定x为f(x)的根。
3. 参考程序 #
#include <iostream> using namespace std; double a,b,c,d; double f(double x){ double f=a*x*x*x+b*x*x+c*x+d; return f; } //枚举法 从-100,-99.99,...,一直枚举到100 void findAns(){ cout<<"枚举:"<<endl; for(double x=-10000;x<=10000;x++){//10000是为了方便x++,也可(x/100)++ double x1=x/100-0.005,x2=x/100+0.005; //if(f(x1)*f(x2)<=0)//有错 在99.99的时候,有99.985; 和99.98的时候,也有99.985, // 如果是99.985,那 99.99和99.98都成立 if(f(x1)*f(x2)<0||f(x1)==0) printf("%.2f ",x/100); } cout<<endl; } //分治 void findAns2(){ cout<<"分治:"<<endl; for(double x=-100;x<=100;x++){ double x1=x,x2=x+1; //先输出等于的情况 if(f(x1)==0) printf("%.2f ",x1); else if(f(x1)*f(x2)<0){//符合条件 while(x2-x1>=0.001){ double mid=(x1+x2)/2; if(x1*mid<=0) x2=mid; else x1=mid; } printf("%.2f ",x1); } } cout<<endl; } int main(){ cin>>a>>b>>c>>d; findAns(); findAns2(); return 0; }