10169. Тернарный поиск
Найдите минимум
функции f(x) = x2 + a * x + b.
Вход.
Два целых числа a и b (|a|, |b| ≤ 106).
Выход.
Выведите значение x, при котором
функция f(x) принимает наименьшее значение.
Ответ выведите с точностью до двух десятичных знаков. Гарантируется, что |x| ≤ 100.
|
Пример входа |
Пример выхода |
|
-2 -35 |
1.00 |
РЕШЕНИЕ
тернарный поиск
Анализ алгоритма
Пусть f(x) –
непрерывная вогнутая функция, имеющая точку локального минимума на отрезке [a; b].
Тернарный поиск позволяет найти эту точку.
Выберем g = a
+ (b – a) / 3, h = a + 2 * (b – a) / 3. Точки g и h
делят отрезок [a; b] на три равные части (отсюда и
название – тернарный поиск). Вычислим значения f(g) и f(h).
·
Если f(g) £ f(h), то
точка минимума функции f лежит на отрезке [a; h], поэтому полагаем b = h.
·
Если f(g) > f(h), то точка минимума лежит на отрезке [g; b], поэтому полагаем a = g.
Процесс продолжается
до тех пор, пока |a – b| > e.
Пример
В примере
задана функция f(x) = x2 – 2 * x – 35
= (x – 7) (x + 5).
Ее корни: x1 = -5, x2
= 7. Минимум
функции достигается при
x = (x1
+ x2) / 2 = (-5 + 7) / 2 = 1
Задачу также
можно решить с помощью математической формулы. Минимум квадратичной функции f(x) = ax2 + bx + c (a > 0) достигается в точке x = -b /
(2a).
Следовательно, для функции f(x) = x2 + a * x + b минимум достигается при x = - a / 2.
Реализация алгоритма
Объявим константу ɛ = 10-7.
#define EPS 0.0000001
Объявим функцию f, минимум которой требуется найти.
double f(double x)
{
return x * x + a * x + b;
}
Функция triple находит минимум функции f(x) на отрезке
[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;
}
Основная часть программы. Читаем входные данные. Запускаем
тернарный поиск. Находим точку минимума функции f(x).
scanf("%lf %lf", &a, &b);
double x = triple(f, -100, 100);
Выводим значение x.
printf("%.2lf\n", x);
Реализация алгоритма -a/2
Читаем входные данные.
scanf("%lf %lf", &a,
&b);
Выводим ответ.
printf("%.2lf\n", -a/2);
Java реализация
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();
}
}