Проиграл Мегафлоп раз, проиграл другой и от стыда сгорел.

Но тут появилась новая проблема! Приехал младший брат Мегафлопа — Гигафлоп. Он работает так быстро, что за ним не угнаться. Давай предложим ребятам придумать такой алгоритм, чтобы все чипы работали одновременно, ни один не стоял без дела.

— А над какой задачей они должны работать? — спросил Сережа.

— И задачу пусть ребята сами придумают. Чипы могут делать что угодно: умножать, делить, сравнивать... из того, что мы научились делать в прошлом году.

— А на конверте пусть ребята напишут «Сразимся с Гигафлопом».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— Молодец! — обрадовался Чип. — Вот ты сам придумал алгоритм двоичного поиска. А теперь попробуй написать программу. Давай воспользуемся командой:

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

— Ишь ты, ни одной ошибки, — сказал Чип, заглянув в листок, — не зря ты учишься в кружке программистов.