Изменения

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

Алгоритм Балабана

840 байт добавлено, 16:36, 1 октября 2013
add some algo
==Алгоритм==
 
Введем несколько дополнительных функций, чтобы упростить основной алгоритм:
 
===Split===
 
Пусть <tex>L = (s_1 ,..., s_k)</tex>, где <tex>s_i <_b s_{i+1}</tex>
<tex>Split_{a,b}(L, Q, L')</tex>
<tex>\{</tex>
<tex>L' \leftarrow 0; Q \leftarrow 0</tex>
'''For''' <tex>j = 1,...,k</tex> '''do'''
'''if''' отрезок <tex>S_j</tex> не пересекает
последний отрезок из <tex>Q</tex> внутри полосы <tex>\langle a, b \rangle</tex>
и при этом содержит её '''then'''
добавить <tex>s_j</tex> в конец <tex>Q;</tex>
'''else'''
добавить <tex>s_j</tex> в конец <tex>L’;</tex>
<tex>\}</tex>
 
===Search In Strip===
==Примечания==
Анонимный участник

Навигация