Пионер 1988-03, страница 64

Сип

(ANS)

Cans)

UJ

fa")

Ш

Двоичный поиск и влюбленный принц

— Апчхи! Ну и пылища!— возмутился Чип, как всегда, появляясь из калькулятора.— Ты что. пере-

9 езжать собрался?

— Нет. у меня генеральная уборка.— вздохнул Сережа.— Ну и скучное же дело! Особенно перебирать шкафы. Я ведь хотел как быстрее: книжки забросил в один, одежду в другой, дверцы прикрыл и пошел гулять. Так бабушка шкафы открыла и за-

^^^^^ ставила перекладывать: чтобы все книги стояли по "Я^Н порядку — по теме, по году издания, по размерам.

I И с одеждой тоже: сначала маленькая, потом по-больше, потом совсем большая — папина... Жуть! И так можно все найти, если постараться: залез, разрыл кучу, нужную вещь вытянул. Пока все книги

® расставишь. они так надоедят, что больше их читать не захочется.

— Не огорчайся. Даже в такой простой жизненной ситуации можно увидеть интересную задачу и придумать красивый алгоритм. А заодно и понять, почему проще постоянно лодцерживать порядок, чем наводить его раз в месяц.

— Какой уж тут алгоритм! Знай рассовывай по шкафам тряпки... Апчхи! Апхчи!

SPC

— Замечательный алгоритм быстрой сортировки. Если у тебя есть, например, пятьсот книг, то он ускорит твою работу в тридцать раз. Давай только начнем издалека. Рассмотрим такую задачу: приятель позвал тебя в гости, номер квартиры сказал, а этаж назвать забыл. Предположим, что он живет в очень высоком, скажем, стоэтажном, доме, где на каждом этаже разное число квартир.

— В Эмпайр-Стейт-Билдинг?

— Пусть там. По числу этажей и количеству почтовых ящиков на первом этаже ничего сказать нельзя. Как бы ты стал искать своего друга?

— По запаху! Раз он меня пригласил, значит, у него пахнет чем-то вкусным.— засмеялся Сережа.— А если говорить серьезно, я бы, наверное, доехал на лифте до верхнего этау<а и стал бы спускаться вниз, проверяя номера на дверях.

— И сколько переходов с этажа на этаж тебе бы потребовалось?

— Ну,— задумался Сережа,— если в доме сто этажей и квартира может оказаться на любом, то в худшем случае я осмотрю все сто, а в среднем, наверное, этажей пятьдесят.

— А я утверждаю, что квартиру твоего друга можно найти не более чем за семь проверок. Помнишь стишок про степени двойки?

— Ты хочешь сказать, что два в седьмой— 128? Но при чем тут это?

— А как чипы справились с Мегафлопом. ты помнишь? Для того чтобы нескольким чипам быстро сложить много чисел, эти числа разбивались на пары, и каждую пару суммировал свой чип, потом суммы снова разбивались на пары и так далее, пока не оставалась сумма всех чисел. Тогда сто чисел мы бы сложили за семь шагов. Если нарисовать график такого суммирования, то получится что-то вроде дерева. А теперь попробуй перевернуть его головой вниз.

— Постой, постой, я, кажется, понял,— обрадовался Сережа.— Мы так определяли день рождения друга. Я должен поехать на пятидесятый этаж, посмотреть там номер квартиры и. если он больше, чем у моего приятеля, поехать вниз, на 25-й, а если меньше, то на 75-й, там опять посмотреть номер квартиры и так далее. Тогда можно за семь шагов найти друга даже в доме со 128 этажами.

— Молодец! — обрадовался Чип.— Вот ты сам придумал алгоритм двоичного поиска. А теперь попробуй написать программу. Давай воспользуемся командой: ПОВТОРЯЙ. ПОКА ВЕРНО УСЛОВИЕ ((БЛОК)) \

Сережа поднатужился и начал писать, косясь при этом на дверь: вдруг войдет бабушка и задаст ему нагоняй за то. что он отлынивает от уборки?

Программа:

1. ВЕРХНИЙ ЭТАЖ = 128.

2. НИЖНИЙ ЭТАЖ = 0.

3. Читай из записной книжки номер квартиры друга.

4. Повторяй, пока ВЕРХНИЙ ЭТАЖ выше НИЖНЕГО.

((СРЕДНИЙ ЭТАЖ = (ВЕРХНИЙ + НИЖНИЙ) : 2,

если ДРУГ живет на СРЕДНЕМ этаже, то КОНЕЦ.

если ДРУГ живет выше СРЕДНЕГО, то НИЖНИЙ этаж приравниваем к СРЕДНЕМУ, иначе

ВЕРХНИЙ приравниваем к СРЕДНЕМУ.))

;

х л m о

0

X

1 Ю О ct

I

а.

" БЛОК — это люОой набор команд а двойные скобки нужны чтобы видеть, где он начинается а где кончается

Н

М

SPC