10169. Ternary search
Find the minimum of the function f(x) = x2 + a * x + b.
Input. Two integers a and b (|a|, |b| ≤ 106).
Output. Print the value of x for
which the function f(x) attains its
minimum. Print the answer with exactly two digits after the decimal point. It
is guaranteed that |x|
≤ 100.
|
Sample
input |
Sample
output |
|
-2 -35 |
1.00 |
SOLUTION
ternary search
Algorithm analysis
Let f(x) be a continuous concave function that
has a local minimum on the interval [a;
b]. Ternary search can be used to
find this point.
Choose g = a + (b
– a) / 3, h = a + 2 * (b – a)
/ 3. The points g and h divide the interval [a; b]
into three equal parts (hence the name “ternary search”). Compute the values f(g) and f(h).
·
If f(g) £ f(h), then the minimum of f lies in the interval [a; h],
so we set b = h.
·
If f(g) >
f(h), then the minimum lies in the
interval [g; b], so we set a = g.
The process continues until |a
– b| > e.
Example
In this example, the function f(x) = x2 – 2 * x – 35
= (x – 7) (x + 5) is given. Its roots are x1
= -5, x2 = 7. The minimum
of the function is attained at
x = (x1 + x2)
/ 2 = (-5 + 7) / 2 = 1
The problem can also be solved using a known formula. The minimum of a
quadratic function f(x)
= ax2 + bx + c (a > 0) is attained at x = -b / (2a).
Therefore, for the function f(x)
= x2 + a * x + b, the
minimum is attained at x = - a / 2.
Algorithm implementation
Define the constant ɛ = 10-7.
#define EPS 0.0000001
Define the function f
whose minimum we want to find.
double f(double x)
{
return x * x + a * x + b;
}
The function triple finds the minimum
of f(x) on the interval [a; b].
double triple(double f(double x), double a, double b)
{
double g, h;
while (b - a > EPS)
{
g = a + (b - a) / 3;
h = a + 2 * (b - a) / 3;
if (f(g) <= f(h)) b = h; else a = g;
}
return (a + b) / 2;
}
The main part of the program. Read the input
data. Run the ternary search. Find the point where the function f(x)
attains its minimum.
scanf("%lf %lf", &a, &b);
double x = triple(f, -100, 100);
Print the value of x.
printf("%.2lf\n", x);
Algorithm implementation -a/2
Read the input data.
scanf("%lf %lf", &a,
&b);
Print the answer.
printf("%.2lf\n", -a/2);
Java implementation
import java.util.*;
public class Main
{
static final double EPS = 0.0000001;
static double a, b;
static double f(double x)
{
return x * x + a * x + b;
}
static double triple(double a, double b)
{
double g, h;
while (b - a > EPS)
{
g = a + (b - a) / 3;
h = a + 2 * (b - a) / 3;
if (f(g) <= f(h)) b = h; else a = g;
}
return (a + b) / 2;
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
a = con.nextDouble();
b = con.nextDouble();
double x = triple(-100,
100);
System.out.printf("%.2f\n",x);
con.close();
}
}