信息学奥赛一本通(1238:一元三次方程求解)

1238:一元三次方程求解


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 6364     通过数: 3241

【题目描述】

形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在−100至100之间),且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。

【输入】

一行,包含四个实数a,b,c,d,相邻两个数之间用单个空格隔开。

【输出】

一行,包含三个实数,为该方程的三个实根,按从小到大顺序排列,相邻两个数之间用单个空格隔开,精确到小数点后2位。

【输入样例】

1.0 -5.0 -4.0 20.0

【输出样例】

-2.00 2.00 5.00

【分析】

        数学中,一个十分基本的问题是求给定方程的解。如下列方程:

        4X^5 - 3X^4 + 2X^3 + 6X^2 + 5X - 7 = 0

        x+ sinx - 3=0

        x^10 -10x = 0

        lgx - x^2 + 7x + 5 = 0

        它们的一般形式可表示为:f(x)=0。方程的根或解是使f(x)等于0的那些x的值。这里,我们仅考虑x为实数的情况。方程f(x)=0可能无根,有单根、多根,甚至有无穷多根。求解这个问题,可以采用枚举法,也可以采用分治法。

        方法1:枚举法。分析一下,根的范围在-100到100之间,以根为枚举对象,枚举范围是-100到100,因为结果要保留两位小数,故此,步长为0.001。 将枚举的根,代入原方程,利用误差法,对原方程式进行一一验证,找出方程的解。

【参考代码1】

#include <stdio.h>
#include <math.h>
double a,b,c,d;
double f(double x)
{
	return ((a*x+b)*x+c)*x+d;
}
int main()
{
	double i;
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	for(i=-100;i<=100;i+=0.001)
	  if(fabs(f(i))<1e-6)
	     printf("%.2lf ",i);
	printf("\n");
	return 0;
}

        方法2:分治法。二分法要求将方程改写成f(x)=0的形式,然后y=f(x)。先选取x1和x2两点,使f(x1)和f(x2)异号。由于y=f(x)是连续不断的曲线,故在x1和x2之间至少有一个根存在。先将可变区间[x1,x2]两等分,求出其中点,即x3=(x1+x2)/2,然后求出函数在中点处的值f(x3)。若f(x3)与f(x1)同号,则新的可变区间就是[x3,x2];如果异号,则新的可变区间是[x1,x3];如果f(x3)=0,则求解完毕。如此重复叠代下去,直至可变区间之长度小于某个预先给定的值为止,或者达到f(x) = 0。 

【参考代码2】

#include<stdio.h>
#include<math.h>
double a,b,c,d;
double F(double x)
{
	return  ((a*x+b)*x+c)*x+d;
}
int main()
{
	int i;
	double x1,x2,xb;
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	for(i=-100;i<=100;i++)
	{
		x1=i;
		x2=i+0.99999;         //注意此处不能用 x2=i+1,否则 else if 分支求一个,if分支又求一个,重复了
		if(fabs(F(x1))<1e-6)
		  printf("%.2lf ",x1);
		else if(F(x1)*F(x2)<0)
		{
			xb=(x1+x2)/2;
			while(fabs(x2-x1)>1e-6)     // x1 != x2,  二分法找到根 
			{
				if(F(x1)*F(xb)>0)
				  x1=xb;
				else
				  x2=xb;
				xb=(x1+x2)/2; 
			}
			printf("%.2lf ",xb); 
		}
	}
	printf("\n");
	return 0;
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1238

上一篇:git初级错误


下一篇:kyxscms框架命令执行