10169. Тернарный поиск

Найдите минимум функции f(x) = x² + a * x + b.

Вход. Два целых числа a и b (|a|, |b| ≤ 10⁶).

Выход. Выведите значение x в котором функция f(x) принимает наименьшее значение. Ответ выведите с 2 десятичными цифрами. Известно, что |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) = x² – 2 * x – 35 = (x – 7) (x + 5). Ее корнями будут x₁ = -5, x₂ = 7. Минимум функции достигается при

x = (x₁ + x₂) / 2 = (-5 + 7) / 2 = 1

Задачу можно решить и при помощи математической формулы. Известно, что минимум функции f(x) = ax² + bx + c (a > 0) достигается при x = -b / (2a). Поэтому для функции f(x) = x² + 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

#include <stdio.h>

double a, b;

int main(void)

{

scanf("%lf %lf", &a, &b);

printf("%.2lf\n", -a/2);

return 0;

}

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();

}

}