1632
правки
Изменения
м
Отрезок Из рассуждений и рисунка может возникнуть идея взять, например, отрезок <tex>[l, a]</tex> брать вместо отрезка <tex>[l, b]</tex>. Но этого делать нельзя, потому что мы не умеем различать случаи, когда <tex>f(a) < f(b)</tex> и <tex>a</tex> слева или справа от минимума.
rollbackEdits.php mass rollback
== Алгоритм ==
[[File:Ternar2.png|thumb|280px|Пример. <tex>f(a) < f(b) \Rightarrow implies x_{min} \in [l, b]</tex>]]
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
<tex> \forall x', x'' \in [l, r]: \\
l < x' < x'' < x_{min} \Rightarrow implies f(l) > f(x') > f(x'') > f(x_{min}) \\x_{min} < x' < x'' < r \Rightarrow implies f(x_{min}) < f(x') < f(x'') < f(r) </tex>.
Значит если <tex>f(a) < f(b)</tex>, то <tex>x_{min} \in [l, b]</tex>,
пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
Можно заметить, что если мы всегда будем брать отрезок <tex>[l, b]</tex> при <tex>f(a) < f(b)</tex> или <tex>[a, r]</tex> при <tex>f(a) > f(b)</tex> , то минимум функции всегда будет в нашем отрезке. Если <tex>f(a) == f(b)</tex>, то можно взять любой отрезок.
=== Псевдокод ===
Рекурсивный вариант:
'''functiondouble''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
'''if''' right - left < eps
'''return''' (left + right) / 2
Итеративный вариант:
'''functiondouble''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
'''while''' right - left > eps
a = (left * 2 + right) / 3
