88
правок
Изменения
Нет описания правки
==Алгоритм==
Рассмотрим одну итерацию алгоритма [[Троичный поиск|троичного поиска]]. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.
[[Файл:divide_seg.gif|220px]]
Пусть <tex>l</tex> и <tex>r</tex> левая и правая граница исследуемого отрезка.
::<tex>x_2 = r - \frac{r - l}{\varphi + 1}</tex>
::и вычислим функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>
[[Файл:new_seg.gif|thumb|380px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]
:'''Шаг 2''':
:: если <tex>f_1 < f_2</tex>, тогда
