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