http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1081. 二分求方程根
时间限制:1.0s   内存限制:512.0MB  
总提交次数:3281   AC次数:939   平均分:29.15
将本题分享到:
   
 
问题描述
  给定一个连续实函数f(x)和一个区间[a, b],已知f(a)*f(b)<0。由微积分的知识可知,在[a, b]上至少存在一个点c,使得f(c)=0,即f(x)在[a, b]区间上至少有一个根。请求出这个根。
  这是一个补充程序的试题,你要完成一个函数
  double getRoot(double (*f)(double), double a, double b)
  并将f(x)=0的在[a, b]区间上的一个根返回,考虑到实数的误差,你只要使得f(x)的绝对值小于10-6(1e-6)即可。
  其中,第一个参数是一个函数指针,所表示的函数将在测试的时候给出,你可以把它看成是如下的函数:
  double f(double x)
  并可以直接调用f(x)来得到这个函数在参数为x时的值。
算法描述
  由于f(x)在[a, b]上连续且f(a)*f(b)<0,所以可以任取[a, b]区间上的一个点p,若f(p)为0(或者绝对值小于10-6),则p为方程的根,否则f(p)一定与f(a)同号(同正负)或与f(b)同号,如果f(p)与f(a)同号,则在[p, b]上存在一个根,否则在[a, p]上存在一个根。
  通过上面的一步,可以将根的范围从[a, b]缩小为[a, p]或[p, b],重复这种方法可以不断缩小根的范围,直到找到根。
  一般情况下,我们取p=(a+b)/2,即每次使用区间的中点进行判断,这种求根的方法叫做二分法。