Игры с Чипом - Мигдал А. А. (версия книг txt) 📗
![Игры с Чипом - isc_8802a.png](https://goldenlib.ru/frontend/web/pic/2/0/8/9/9/3/208993/1402864671/isc_8802a.png)
Так же и из вас, медленных чипов, собирают параллельные машины, а мы, программисты, ломаем потом голову: как распределить работу, чтобы вы все решали одну задачу, но каждый делал свои кусок и не зависел от товарищей. Все крупнейшие современные машины устроены по такому принципу. Предложите вашему Мегафлопу соревноваться. Например, сложить, кто быстрее, тысячу чисел. Он будет суммировать их все подряд, а вы сделайте так, как я нарисовал. Вы вместе за десять шагов сложите всю тысячу потому, что вас много, а я дал вам хороший параллельный алгоритм».
![Игры с Чипом - isc_8802b.png](https://goldenlib.ru/frontend/web/pic/2/0/8/9/9/3/208993/1402864671/isc_8802b.png)
— Погоди-ка, — перебил Чипа Сережа. — Ведь тысяча — это не степень двойки. Разделил пополам — 500, сложил 500 пар, разделил на 250 пар, снова попарно сложил, разделил на 125 пар, сложил — и стоп! Дальше не делится! Не додумал твой Леня алгоритм.
— Молодец, — усмехнулся Чип, — не зря я тебя учил. Что же, в этом случае проще всего добавить три числа, равных нулю.
— А зачем нули добавлять?
— Чтобы всем чипам работа досталась. Сумма не изменится, а слагаемых станет 128, их можно до конца разбивать на пары. А еще проще, как только количество чисел становится нечетным, к ним добавляется еще одно число, равное нулю.
— Удивительно! Вроде лишнюю работу делаем, а получается быстрее.
— Зато все чипы при деле, в ногу шагают! — Чип подмигнул Сереже и продолжил: - Так мы и сделали, а потом и сами предложили Мегафлопу вторую задачу: найти наибольшее из тысячи чисел. (Кстати, как это сделать за десять шагов?) Потом третью: вывести оценки за четверть для всей школы (для каждого ученика его оценка за четверть по каждому предмету есть среднее арифметическое его оценок, полученных в течение четверти). Как, по-твоему, мы решили эту задачу?
Проиграл Мегафлоп раз, проиграл другой и от стыда сгорел.
Но тут появилась новая проблема! Приехал младший брат Мегафлопа — Гигафлоп. Он работает так быстро, что за ним не угнаться. Давай предложим ребятам придумать такой алгоритм, чтобы все чипы работали одновременно, ни один не стоял без дела.
— А над какой задачей они должны работать? — спросил Сережа.
— И задачу пусть ребята сами придумают. Чипы могут делать что угодно: умножать, делить, сравнивать... из того, что мы научились делать в прошлом году.
— А на конверте пусть ребята напишут «Сразимся с Гигафлопом».
Двоичный поиск и влюбленный принц
— Апчхи! Ну и пылища! — возмутился Чип, как всегда, появляясь из калькулятора. — Ты что, переезжать собрался?
— Нет, у меня генеральная уборка, — вздохнул Сережа. — Ну и скучное же дело! Особенно перебирать шкафы. Я ведь хотел как быстрее: книжки забросил в один, одежду в другой, дверцы прикрыл и пошел гулять. Так бабушка шкафы открыла и заставила перекладывать: чтобы все книги стояли по порядку — по теме, по году издания, по размерам. И с одеждой тоже: сначала маленькая, потом побольше, потом совсем большая — папина... Жуть! И так можно все найти, если постараться: залез, разрыл кучу, нужную вещь вытянул. Пока все книги расставишь, они так надоедят, что больше их читать не захочется.
— Не огорчайся. Даже в такой простой жизненной ситуации можно увидеть интересную задачу и придумать красивый алгоритм. А заодно и понять, почему проще постоянно поддерживать порядок, чем наводить его раз в месяц.
— Какой уж тут алгоритм! Знай рассовывай по шкафам тряпки... Апчхи! Апхчи!
— Замечательный алгоритм быстрой сортировки. Если у тебя есть, например, пятьсот книг, то он ускорит твою работу в тридцать раз. Давай только начнем издалека. Рассмотрим такую задачу: приятель позвал тебя в гости, номер квартиры сказал, а этаж назвать забыл. Предположим, что он живет в очень высоком, скажем, стоэтажном, доме, где на каждом этаже разное число квартир.
— В Эмпайр-Стейт-Билдинг?
— Пусть там. По числу этажей и количеству почтовых ящиков на первом этаже ничего сказать нельзя. Как бы ты стал искать своего друга?
— По запаху! Раз он меня пригласил, значит, у него пахнет чем-то вкусным, — засмеялся Сережа. — А если говорить серьезно, я бы, наверное, доехал на лифте до верхнего этажа и стал бы спускаться вниз, проверяя номера на дверях.
— И сколько переходов с этажа на этаж тебе бы потребовалось?
— Ну, — задумался Сережа,— если в доме сто этажей и квартира может оказаться на любом, то в худшем случае я осмотрю все сто, а в среднем, наверное, этажей пятьдесят.
![Игры с Чипом - isc_8803b.png](https://goldenlib.ru/frontend/web/pic/2/0/8/9/9/3/208993/1402864671/isc_8803b.png)
— А я утверждаю, что квартиру твоего друга можно найти не более чем за семь проверок. Помнишь стишок про степени двойки?
— Ты хочешь сказать, что два в седьмой — 128? Но при чем тут это?
— А как чипы справились с Мегафлопом, ты помнишь? Для того чтобы нескольким чипам быстро сложить много чисел, эти числа разбивались на пары, и каждую пару суммировал свой чип, потом суммы снова разбивались на пары и так далее, пока не оставалась сумма всех чисел. Тогда сто чисел мы бы сложили за семь шагов. Если нарисовать график такого суммирования, то получится что-то вроде дерева. А теперь попробуй перевернуть его головой вниз.
— Постой, постой, я, кажется, понял, — обрадовался Сережа. — Мы так определяли день рождения друга. Я должен поехать на пятидесятый этаж, посмотреть там номер квартиры и, если он больше, чем у моего приятеля, поехать вниз, на 25-й, а если меньше, то на 75-й, там опять посмотреть номер квартиры и так далее. Тогда можно за семь шагов найти друга даже в доме со 128 этажами.
— Молодец! — обрадовался Чип. — Вот ты сам придумал алгоритм двоичного поиска. А теперь попробуй написать программу. Давай воспользуемся командой:
ПОВТОРЯЙ, ПОКА ВЕРНО УСЛОВИЕ ((БЛОК))
Сережа поднатужился и начал писать, косясь при этом на дверь: вдруг войдет бабушка и задаст ему нагоняй за то, что он отлынивает от уборки?
Программа:
1. ВЕРХНИЙ ЭТАЖ = 128.
2. НИЖНИЙ ЭТАЖ = 0.
3. Читай из записной книжки номер квартиры друга.
4. Повторяй, пока ВЕРХНИЙ ЭТАЖ выше НИЖНЕГО.
((СРЕДНИЙ ЭТАЖ = (ВЕРХНИЙ + НИЖНИЙ) : 2.
если ДРУГ живет на СРЕДНЕМ этаже, то КОНЕЦ,
если ДРУГ живет выше СРЕДНЕГО, то НИЖНИЙ этаж приравниваем к СРЕДНЕМУ,
иначе ВЕРХНИЙ
приравниваем к СРЕДНЕМУ.))
— Ишь ты, ни одной ошибки, — сказал Чип, заглянув в листок, — не зря ты учишься в кружке программистов.
— Только какое это имеет отношение к уборке? — отложив ручку, спросил Сережа.
— Самое прямое! — успокоил его Чип. — Давай разберем еще одну задачку. Ты читал сказку Шарля Перро «Золушка»?
— Спрашиваешь!
— Тогда ты, конечно, помнишь, что принц приказал мерить туфельку всем девушкам королевства. Сначала принцессам, потом герцогиням, потом придворным дамам... А теперь посчитаем. Во Франции порядка миллиона девушек нужного возраста. Если каждая будет мерить туфельку хотя бы в течение минуты, то вся процедура примерки займет около трех лет, и это при условии, что принц будет работать не покладая рук день и ночь. Только сказочная любовь может выдержать подобное испытание. А теперь предположим, что мы с тобой советники короля. Если бы девушек можно было построить, но не по росту, а по размеру ноги, что бы ты предложил принцу?
7
БЛОК - это любой набор команд, а двойные скобки нужны, чтобы видеть, где он начинается, а где кончается.