Page 79 - Bkhargava_-_Grokaem_algoritmy

78 Глава 4. Быстрая сортировка

Теперь нужно вычислить рекурсивный случай. Здесь-то вам на помощь
и приходит стратегия «разделяй и властвуй ~ . В соответствии с ней при
каждом рекурсивном вызове задача должна сокращаться. Как сократить
эту задачу? Для начала разметим самые большие участки, которые можно

использовать.

НЕ.РКПРЕ.­
.О.6А .ll.Е.ЛЕ.ННЫК
УЧАСТК~ ????
ОС.ТАТОК
~

..._______, С.........--..... т.-___ _..J---..--"
<O М <O м 1100 м

В исходном наделе можно разместить два участка 640 х 640, и еще останется
место. Тут-то и наступает момент истины. Нераспределенный остаток - это
тоже надел земли, который нужно разделить. Так почему бы не применить
к нему тот же алгоритм?

6lt0 м

ltOO м

НО6ЫК НUЕ.Л, КОТОРЫК ТО#.Е.
НУ~но РАЗБИТЬ НА УЧАСТКИ

Итак, мы начали с надела 1680 х 640, который необходимо разделить на
участки. Но теперь разделить нужно меньший сегмент - 640 х 400. Если

www.trk.kg