Given a cubic
equation ax3 + bx2 + cx + d
= 0 (a ≠ 0). It is known
that this equation has exactly one root. Find it.
Input. Four integers: a, b, c,
d (-1000 ≤ a, b, c, d
≤ 1000).
Output. Print the
root of equation with no less than 6 decimal digits.
|
Sample
input |
Sample
output |
|
-1 -6 -12 -7 |
-1.0000000111 |
binary search
Localize the root
of equalization f(x) = 0. To do this,
find r such that f(-r)
* f(r) < 0. For example, having
initialized r = 1, we will double r at each step
until holds
an inequality f(-r)
* f(r) < 0. Thus, we will iterate
over intervals [-1; 1], [-2; 2], [-4; 4], [-8; 8], …. until we find the interval where the root of the
equation is
located.
Set l = -r. Further
on the interval [l; r]
using a binary search (dividing a segment in half), we look for a root.
Declare the constant
epsilon.
.
#define EPS 1e-12
Function f computes the value of a cubic
polynomial.
double f(double
x)
{
return
a*x*x*x + b*x*x + c*x + d;
}
The main part of
the program. Read the input
data.
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
Find the boundaries [l; r] containing the
desired root. Initially set r = 1. Sequentially increase r twice until the desired root will
belong to the interval [-r;
r] (for this it is necessary that the
function f(x) will take the opposite sign values at
the ends of the interval). Then set l = -r.
r = 1;
while(f(r) * f(-r) >= 0) r *= 2;
l = -r;
Using binary search, we search for
the root of equation f(x) = 0 on the
interval [l;
r].
while (r - l > EPS)
{
x = (l + r) / 2;
if (f(x) *
f(r) > 0) r = x; else l = x;
}
Print the answer.
printf("%.8lf\n",l);
Java realization
import java.util.*;
public class Main
{
static double a, b, c, d;
static double f(double x)
{
return a*x*x*x + b*x*x + c*x + d;
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
a = con.nextDouble();
b = con.nextDouble();
c = con.nextDouble();
d = con.nextDouble();
double right = 1;
while(f(right) * f(-right) >= 0) right *= 2;
double left = -right;
while (right - left > 1e-6)
{
double middle = (left + right) / 2;
if (f(middle) * f(right) > 0) right = middle;
else left = middle;
}
System.out.println(left);
con.close();
}
}