Все это Чип успел рассказать сам себе за ту секунду, которая потребовалась Сереже, чтобы ответить:
— Да. на целых пять сантиметров. А ты почему не растешь? Когда ты станешь таким же большим, как твой папа — Центральный процессор?
— Мы, чипы, не растем, а сразу рождаемся взрослыми: большими или маленькими, умными или глупыми, быстрыми или медленными. Но бывает так, что несколько медленных чипов оказываются быстрее одного быстрого.
— Десять черепах обгоняют одного зайца?
— Почти так, но поскольку машины сами думать не умеют, им должен помочь хороший программист. Вот как-то раз приехал к нам из-за границы нахальный чип Мегафлоп. Был он маленький, гладкий и все ходил и похвалялся: «Эх вы, старикашки! Вам бы на пенсию или в демонтаж! Краска облуплена, час поработаете и перегреваетесь, а уж считаете вы совсем как черепахи. Пока вы два числа сложите, я — сто, пока вы два числа умножите, я — двести. На что вы годны?!» Обидно нам стало, и решили мы пойти к программисту Лене и попросить помощи — неужто и правда нами можно только гвозди забивать?
Леня засмеялся и сказал: «Чипы! Решите-ка такую задачу: по длинной улице идут сплошным потоком машины. Между каждой парой машин может проскочить один человек. За какое время перейдет на другую сторону улицы рота солдат, если один человек перебегает улицу за десять секунд?». «За тысячу секунд», — хором ответили чипы. «Ну и неверно! Кто вам мешает построить солдат вдоль улицы, и тогда вся рота перейдет за десять секунд.
Так же и из вас, медленных чипов, собирают параллельные машины, а мы, программисты, ломаем потом голову: как распределить работу, чтобы вы все решали одну задачу, но каждый делал свои кусок и не зависел от товарищей. Все крупнейшие современные машины устроены по такому принципу. Предложите вашему Мегафлопу соревноваться. Например, сложить, кто быстрее, тысячу чисел. Он будет суммировать их все подряд, а вы сделайте так, как я нарисовал. Вы вместе за десять шагов сложите всю тысячу потому, что вас много, а я дал вам хороший параллельный алгоритм».
— Погоди-ка, — перебил Чипа Сережа. — Ведь тысяча — это не степень двойки. Разделил пополам — 500, сложил 500 пар, разделил на 250 пар, снова попарно сложил, разделил на 125 пар, сложил — и стоп! Дальше не делится! Не додумал твой Леня алгоритм.
— Молодец, — усмехнулся Чип, — не зря я тебя учил. Что же, в этом случае проще всего добавить три числа, равных нулю.
— А зачем нули добавлять?
— Чтобы всем чипам работа досталась. Сумма не изменится, а слагаемых станет 128, их можно до конца разбивать на пары. А еще проще, как только количество чисел становится нечетным, к ним добавляется еще одно число, равное нулю.
— Удивительно! Вроде лишнюю работу делаем, а получается быстрее.
— Зато все чипы при деле, в ногу шагают! — Чип подмигнул Сереже и продолжил: - Так мы и сделали, а потом и сами предложили Мегафлопу вторую задачу: найти наибольшее из тысячи чисел. (Кстати, как это сделать за десять шагов?) Потом третью: вывести оценки за четверть для всей школы (для каждого ученика его оценка за четверть по каждому предмету есть среднее арифметическое его оценок, полученных в течение четверти). Как, по-твоему, мы решили эту задачу?
Проиграл Мегафлоп раз, проиграл другой и от стыда сгорел.
Но тут появилась новая проблема! Приехал младший брат Мегафлопа — Гигафлоп. Он работает так быстро, что за ним не угнаться. Давай предложим ребятам придумать такой алгоритм, чтобы все чипы работали одновременно, ни один не стоял без дела.
— А над какой задачей они должны работать? — спросил Сережа.
— И задачу пусть ребята сами придумают. Чипы могут делать что угодно: умножать, делить, сравнивать... из того, что мы научились делать в прошлом году.
— А на конверте пусть ребята напишут «Сразимся с Гигафлопом».
Двоичный поиск и влюбленный принц
— Апчхи! Ну и пылища! — возмутился Чип, как всегда, появляясь из калькулятора. — Ты что, переезжать собрался?
— Нет, у меня генеральная уборка, — вздохнул Сережа. — Ну и скучное же дело! Особенно перебирать шкафы. Я ведь хотел как быстрее: книжки забросил в один, одежду в другой, дверцы прикрыл и пошел гулять. Так бабушка шкафы открыла и заставила перекладывать: чтобы все книги стояли по порядку — по теме, по году издания, по размерам. И с одеждой тоже: сначала маленькая, потом побольше, потом совсем большая — папина... Жуть! И так можно все найти, если постараться: залез, разрыл кучу, нужную вещь вытянул. Пока все книги расставишь, они так надоедят, что больше их читать не захочется.