一元三次方程 （codevs 1038）题解

【问题描述】

     有形如：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)之间一定有一个 根。

【样例输入】

    1 -5 -4 20

【样例输出】

   -2.00 2.00 5.00

【解题思路】

     本题为NOIP2001 提高组第二题，可用两种方法解决，枚举/二分，但老师改了一下数据，将保留2位改为了保留4位，导致枚举会超时，无奈之下用了二分……这里还是讲保留2位小数。题目中的提示已经完完全全告诉了我们思路，设f(x)=a*x^3+b*x^2+c*x+d，若用枚举，从-100开始，每次加0.01，按题目说明，如果f(x-0.005)*f(x+0.005)<0,那么，x即是答案(题目要求保留两位小数，只需write的时候加上:0:2即可，无需再判断x），或者f(x)本身就等于0，x也是答案。详见代码。

   下面为二分题解。

      二分是由分治策略引申的一种解题方法，比枚举会更快一些，所谓二分，就是将题目从中间分为两个部分，再对左右两边的分问题进行解答，将最终答案递归回来即可。

      提示又给了我们很好的思路，这就是典型的二分了。如果f(x1)*f(x2)<0或者x1+1>x2，那么就从中间分为两个部分，为什么是或者呢？题目中说根与根的差的绝对值>=1，因此，如果我们找的两个数的差大于1，那么有可能这两个数中间不止存在一个解，因此也需要二分，利用这个特性，我们可以之间将-100与100二分。终止条件：(f(x)=0)or((x1+0.001>x2)and(f(x1)*f(x2)<0)这里的终止条件与枚举不同，但原理是一样的同样是因为需要保留两位小数，因此需要判断三位。详见代码。

【代码实现】

var a,b,c,d,x:real;
    w:integer;
function f(x1:real):real;
begin
 f:=a*x1*x1*x1+b*x1*x1+c*x1+d;
end;
begin
 x:=-100;
 readln(a,b,c,d);
 repeat
  x:=x+0.01;
  if (f(x)=0) or (f(x-0.005)*f(x+0.005)<0) then//注意这里的条件，有两种情况都算作根
   begin
    write(x:0:2,'  ');
    inc(w);
   end;
 until w=3;
end.

var a,b,c,d:double;
    i:longint;
function js(x:double):double;
begin
 js:=a*x*x*x+b*x*x+c*x+d;
end;
procedure try(x1,x2:double);
var x0,y0,y1,y2:double;
begin
 x0:=(x1+x2)/2;
 y0:=js(x0);y1:=js(x1);y2:=js(x2);
 if (y0=0)or((x1+0.001>x2)and(y1*y2<0))then//满足条件，输出
  begin
   write(x0:0:2,' ');
   exit;
  end;
 if (y1*y0<0)or(x0-x1>1) then//注意题中说了两个解之间的差的绝对值>=1，所以递归的条件不只是单纯的f(x1)*f(x0)<0
  try(x1,x0);
 if (y0*y2<0)or(x2-x0>1) then
  try(x0,x2);
end;
begin
 readln(a,b,c,d);
 try(-100,100);
end.