Изменения

Перейти к: навигация, поиск

Троичный поиск

172 байта добавлено, 19:05, 4 сентября 2022
м
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, a]</tex> брать вместо отрезка <tex>[l, b]</tex>. Но этого делать нельзя, потому что мы не умеем различать случаи, когда <tex>f(a) < f(b)</tex> и <tex>a</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>, то можно взять любой отрезок.
=== Псевдокод ===
1632
правки

Навигация