Текст книги "Игры с Чипом"

Автор книги: Пионер Журнал

Совет Чеширского кота

– Чип, что-то давно ты мне сказок не рассказывал, а они у тебя такие интересные получаются!

– О чем же тебе рассказать? Хочешь опять про Алису?

Сережа молча кивнул и приготовился слушать.

– Итак, я расскажу тебе про рыцарский турнир в стране чудес, – начал Чип и тут же сам себя перебил: – А ты знаешь, кстати, что автор «Алисы в стране чудес» и «В Зазеркалье» Льюис Кэрролл на самом деле был Чарлзом Доджсоном, профессиональным математиком, и всерьез занимался теорией турниров?

– Как это теорией турниров? – удивился Сережа. – Турнир – он и есть турнир, сражайся, пока всех не одолеешь, вот и вся теория.

– Вот как? А если твои противники со свежими силами, а ты с каждым боем все больше устаешь? И потом зачем всем рыцарям стоять без дела, пока двое сражаются? Другие пары тоже могут сражаться. Это, брат, целая наука, как провести турнир быстро и справедливо. Вот послушай-ка про один такой турнир в стране чудес.

«Король с утра был в дурном расположении духа. Завтра начинался ежегодный рыцарский турнир, на который съезжались рыцари со всех концов страны. Само по себе это было хорошо, но вот беда, рыцарей в этот раз съехалось уж слишком много – пятьсот двенадцать человек, не считая челяди и оруженосцев. По старым турнирным правилам каждый рыцарь мог сражаться с любыми другими до тех пор, пока не объявится такой рыцарь, вызов которого никто не решится принять. Но сейчас рыцарей было слишком много для таких правил!

– Представляешь, дорогая, – сказал король королеве, – если один рыцарь захочет сразиться со всеми остальными, то это займет 512 дней!

– Пятьсот  одиннадцать, –  возразила  королева, – ведь сам с собой он не станет сражаться.

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

– Ах, какой ужас, – воскликнула королева, – ведь нам придется все это время их еще и кормить! Нет, это невозможно, надо что-то придумать. Может быть, посоветуемся с Чеширским котом? У него иногда бывают прекрасные идеи.

– Представь себе, эта мысль мне уже пришла в голову, и я с ним посоветовался сегодня утром. Но на этот раз он ничего путного не сказал, если не считать дурацкого стишка. Он прочел его в своей обычной загадочной манере и растаял в воздухе прежде, чем я успел задать хоть один вопрос.

– А ты запомнил этот стишок?

– Изволь, дорогая, я могу его прочесть.

 
Пятьсот двенадцать рыцарей собрались на турнир,
Чтоб самого достойного узнал волшебный мир.
Они сразились по двое, и до исхода дня
Из каждой пары рыцарей один упал с коня.
И если будут рыцари все так же продолжать,
То сколько дней осталось им друг с другом воевать?
 

– Знаешь, дорогой, это определенно должно нам помочь, ведь тут тоже 512 рыцарей, как и у нас. Вот только непонятно, как они сражались и сколько времени занял турнир. Может быть, спросим у наших рыцарей? И того, кто отгадает, объявим победителем турнира.

– Ах, что ты, во-первых, им ни за что не отгадать, а во-вторых, они специально сюда приехали, чтобы подраться, и без боя не уедут. Послушай, а что, если спросить Алису?

– Эту скверную девчонку с дурными манерами? – вмешалась возмущенная герцогиня. – Она и крокетного фламинго толком держать не умеет!

– Да, вы правы, милая герцогиня, но нельзя при этом отрицать, что пару раз она нам помогла. Позвать сюда Алису!

– Только и всего? – рассмеялась Алиса, услышав стишок. – Но тут же ясно сказано, как надо сражаться: по двое, все одновременно, а проигравший выбывает. И займет это... дайте подумать...»

– А пока Алиса думает, – продолжал Чип, – мне хотелось бы показать тебе одно письмо. Нас ругает сердитый семиклассник из города Свалява Закарпатской области, который не указал своего имени и обратного адреса, наверное, чего-то испугался. Он пишет: «Ваши темы не заинтересуют даже ученика третьего класса. Нужно сначала выучить язык, какую-нибудь паршивенькую «Рапиру» хотя бы знать досконально, а потом уж разглагольствовать. Моя десятилетняя сестра знает БЕЙСИК, изучает ФОРТРАН 77. Она написала программы для решения уравнений – квадратных, линейных и так далее. Ей смешно читать про «Теремок», про «Красную шапочку», я не говорю уже о себе».

– Прекрасно, – подхватил Сережа, – пусть он нам напишет программу турнира Чеширского кота на любом языке. А чтобы письмо этого сердитого читателя не затерялось в нашей большой почте, на конверте пусть он поставит фразу: «Чип, это я»– и обведет ее рамочкой. Впрочем, все ребята тоже могут принять участие в конкурсе, только на конверте пусть просто напишут «Турнир».

ОТ РЕДАКЦИИ:

Ребята! В № 6 за этот год вы увидели фотографии победителей «Конкурса Чипа». А вот как выглядит ПРОГРАММИРУЕМЫЙ НАУЧНЫЙ КАЛЬКУЛЯТОР – приз Кирилла Мишачева.

Такому калькулятору можно задать 40 команд, и он выполнит их все подряд. Например, если вам в школе дали на дом 20 задач на умножение простых дробей, решите на калькуляторе только первую задачу, а с остальными он справится сам, вам останется только вводить в него числа.

Этот калькулятор умеет решать многое из того, что знают старшеклассники и студенты. А младшие школьники могут с ним играть в «Чет – нечет», «20 спичек и монетку» и другие игры. Калькулятор ни разу не ошибется и всегда обыграет вас.

В № 12 за этот год Чип объявит новый БОЛЬШОЙ КОНКУРС. Победителей конкурса ждут призы – КАЛЬКУЛЯТОРЫ.

Вы готовы принять участие в конкурсе?

Случайные числа

– Чип, а не скучно вам, компьютерам, все время иметь дело с числами? Все заранее известно, никаких неожиданностей и случайностей.

– А ты знаешь, что самые сложные задачи, которые решаются на компьютерах – называются они моделирование больших систем, – основаны именно на случайных числах?

– Как это? Я думаю, что чем сложнее система, тем больше приходится считать. А при чем же тут случайные числа?

– Случайные числа не нужны для точных расчетов, но они нужны, чтобы моделировать случайные процессы. А таких процессов великое множество: почти все явления природы и человеческой жизни. Например, голубой цвет неба связан с тем, что лучи других цветов, сильнее рассеиваясь на случайно расположенных молекулах в атмосфере, не достигают наших глаз. Другой пример, из жизни. Как прогнозировать образование очередей или транспортных пробок? Это тоже случайные процессы, поскольку каждый человек принимает решения по одному ему известным соображениям.

– Так что же, получается полный хаос? – Сережа вставил новое слово, которое он недавно где-то услышал. – Может быть так, а может быть иначе? Чем же тут поможет компьютер?

– А компьютер поможет сосчитать вероятности того, будет это так или иначе.

– И как же компьютер это сделает?

– Ну, возьмем простой пример случайного процесса. Когда ты после телефонного разговора вешаешь телефонную трубку, ты обычно не смотришь, как закручен провод, верно? Поэтому после каждого нового разговора он может либо закрутиться еще на один оборот, либо остаться на месте, либо раскрутиться назад на один оборот.

– Он еще может совсем раскрутиться, если папа заметит, что провод слишком сильно закрутился, и не поленится его раскрутить.

– Давай для начала пренебрежем таким редким событием, а остальные три варианта – шаг вперед, шаг назад и шаг на месте – будем считать равновероятными. Это целая наука, как получать на компьютере случайные числа, – для этого лучшие программисты придумывают самые быстрые алгоритмы. Ну, а мы с тобой можем воспользоваться сейчас игральным кубиком. На нем ведь шесть чисел: 1, 2, 3, 4, 5, 6. Давай будем делать шаг назад, если на кубике выпадет 1 или 2, оставаться на месте, если это 3 или 4, и делать шаг вперед, если это 5 или 6.

– Давай. Ты будешь складывать шаги, а я буду кидать кубик, – оживился Сережа, которому немного наскучили лекции Чипа и захотелось поиграть.

Сережа бросил кубик. Выпало 5, и он крикнул Чипу: «Вперед!» «Один!» – крикнул в ответ Чип.

Сережа кинул кубик еще раз. «Стой!» – крикнул он, потому что выпало 3. «Один!» – повторил Чип предыдущий счет. Дальше дело пошло быстрее: «Вперед!» «Два». «Назад!» «Один». «Стой!» «Один» «Вперед!» «Два». «Вперед!» «Три». «Стой!» «Три». «Вперед!» «Четыре». «Назад!» «Три».

– Ну, что, – сказал Чип,– мы бросили кубик 10 раз и сдвинулись вперед на 3 шага. Значит, провод закрутился бы на 3 оборота. Будем считать, что после каждых 10 звонков папа проверяет провод и раскручивает его. Начнем все сначала.

Они кинули кубик еще 10 раз. Теперь получилось в сумме 2 шага назад, то есть провод закрутился бы на два оборота в другую сторону. Еще и еще кидали они кубик, и получилось, что за 10 бросаний кубика суммарное число шагов бывало в среднем 3 – 4, а направление бывало разным – иногда вперед, а иногда назад. Всего они сделали 10 опытов по 10 бросаний, и в 5 опытах было положительное направление, в 4 – отрицательное, а в одном опыте после всех 10 бросаний кубика получился нуль, так что провод совсем бы не закрутился. Но это, конечно, была редкая удача.

– Видишь, – сказал Чип, – кое-что мы поняли. Ваш телефонный провод будет со временем закручиваться, иногда в одну, а иногда в другую сторону, но количество оборотов будет расти, так что папе время от времени придется его раскручивать обратно. А если бы мы с тобой бросили кубик миллиард раз вместо ста, то смогли бы точно подсчитать, как величина закрутки зависит от времени и как часто папе придется раскручивать провод. Вот для того, чтобы быстро сделать миллиард таких испытаний, и нужен компьютер. Кстати, в этом простом случае и без компьютера можно предсказать, что величина закрутки провода будет расти, как корень квадратный из времени.

– Давай теперь сделаем что-нибудь смешное, я хочу немного посмеяться, а то надоело с числами возиться.

– Ты любишь играть в чепуху? Это когда несколько человек пишут каждый свой рассказ, меняясь по кругу бумажками после каждого слова и загибая бумажки, чтобы не подглядывать.

– Да, здорово было бы сыграть, только нас всего двое – так неинтересно!

– А вот с помощью случайных чисел можно играть в чепуху даже одному. Сочиняешь шесть разных рассказов, а потом составляешь один, по очереди выдергивая слова из случайно выбранного рассказа. А из какого рассказа выдернуть очередное слово, решаешь, бросая игральный кубик.

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

1. Шел снег. Усталый мальчик брел из школы домой насвистывая.

2. Была жара. Веселый воробышек прыгал с ветки на ветку чирикая.

3. Моросил дождь. Огромный кит плыл из моря в океан пыхтя.

4. Лил дождь. Свирепый динозавр выползал из болота рыча.

5. Стоял туман. Сверкающий автомобиль мчался из города на дачу гудя.

6. Надвигалась буря. Озабоченный шмель летел с поля в сад жужжа.

В каждом рассказе было по 10 слов, так что кубик опять пришлось бросать 10 раз. У Чипа получилось: «Стоял снег. Веселый динозавр прыгал с ветки на дачу насвистывая». А у Сережи: «Надвигалась жара. Свирепый шмель плыл с поля домой пыхтя».

Отсмеявшись над своими рассказами, Чип и Сережа придумали такое задание для читателей: сочинить смешную игру, где применялся бы принцип случайных чисел. Лучшая игра будет опубликована в журнале. На конверте укажите: «Случайные числа».

До свиданья, друзья!

Вот и кончается 1987 год. За этот год Сережа узнал много нового и всерьез увлекся информатикой. Он поступил в кружок программистов и научился сам писать программы на языке Бейсик. Теперь настоящий, взрослый компьютер его слушается! Например, попросишь компьютер нарисовать на экране двух рыбок, которые друг за другом гоняются, – и, пожалуйста, бегают по экрану, как живые.

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

Хотите знать, как пишется такая программа? На экране компьютера каждая строчка пронумерована, а в каждой строчке пронумерована каждая буква. Всего в строчке, скажем, 80 букв, вернее, позиций – мест для буквы.

Скажешь компьютеру: «Напиши букву О на 3-й позиции 5-й строчки», – он ее напишет. А если скажешь: «Напиши знак >, а за ним букву О», – то получится маленькая рыбка.

Рыбка:

>O

Ну, а щука получится, если нарисовать знак > , два знака равенства, верхнюю кавычку и знак <.

Щука:

>=='<

Если нарисовать щуку, начиная, скажем с 3-й позиции, а маленькую рыбку – с 9-й, то получится погоня.

  >=='< >O

1234567891011

Сережа научил их отталкиваться от стенок, нырять, отдаляться и приближаться друг к другу. Потом он нарисовал голубую воду и зеленые водоросли. Наконец, он сделал так, чтобы щука щелкала пастью.

Жаль, что нельзя показать, какой красивый мультфильм получился!

Зато можно показать кадр из другого мультфильма, сделанного большим компьютером в Институте космических исследований Академии наук СССР. Это Фобос – маленький спутник Марса. Американская космическая станция «Викинг» сделала несколько его фотографий, которые были обработаны на нашем компьютере, так что получилась объемная модель. Ее можно было вращать и разглядывать со всех сторон.

Через 2 года на Марс полетит советская космическая станция, которая со всех сторон облетит Фобос и рассмотрит его вблизи. Этот компьютерный мультфильм нужен для навигации – наша станция будет сверять вид из окна с кадром из мультфильма, чтобы знать, где она находится и куда ей лететь дальше.

– А где же Чип? – спросите вы. У Чипа тоже интересные события. Он как раз и собирается лететь на Марс на космической станции и управлять полетом над Фобосом. Теперь Чип не сможет так часто играть с Сережей. Но они по-прежнему большие друзья и любят в свободный часок поболтать и пофантазировать. А что из этого получится, вы узнаете в новом году.

Нам осталось подвести итоги конкурсов этого года и объявить новый конкурс.

«Поможем Шерлоку Холмсу»

Правильных программ вы прислали много, но 90% из них дословно повторяют то, что было в «Пионере». Ребята, думайте сами!А то в XXI веке вам будет стыдно перед компьютерами.

Вот кто прислал оригинальные решения: Инесса БАГДАСАРЯН из Еревана, Таня АСИЛЬЕВА из Тольятти, Наташа АКИМОВА из Ленинграда, Ирина РОСПАШНЮК из города Фалешты Молдавской ССР, Алексей БЕЛОНОГОВ из Иркутска, А. ЧИЖОВ из Львова, Наталья ЗАВАЛИШИНА из Нижнего Тагила, Д. УГАЙ из поселка имени Морозова Всеволожского района Ленинградской обл., Наташа ВЯТКИНА из г. Сегежа Карельской АССР и Аня КРОЛ из Москвы.

«Роза для Королевы»

На это задание мы не получили ни одной правильной программы, но в трех работах есть интересные идеи. Лина РОСТОВСКАЯ из Москвы, ученица 4-го класса, предложила совершенно оригинальный алгоритм выбора розы с помощью двух палочек. Молодец, Лина! Только в следующий раз попробуй вместо слов «и так будет дальше все время» написать цикл, как мы делали в «Пионере». Аня КРОЛ, которая отличилась и в конкурсе «Шерлока Холмса», тоже прислала интересную работу, написанную белым стихом. Она предлагает разбирать розы на пары, как и Лина, но ее алгоритмы немного сложнее и менее четкие, чем у Лины. Зато она придумала отдельно повязывать лентой непарные розы и потом их тоже сравнивать с лучшей.

Таня САЯПИНА также прислала интересное письмо с правильными идеями и красивым рисунком. Она спрашивает: правда ли, что компьютеры ошибаются?

Вот что по этому поводу думает Чип: «Мы ошибаемся, но гораздо реже, чем люди, и обычно в этом виноваты не мы. Например, если нам написали неверную программу, разве мы виноваты? А еще обиднее, когда прыгает напряжение в сети: считаешь, считаешь, а тут тебе, как обухом по голове, конечно, собьешься. Так что если вы, люди, будете аккуратными, то и мы не будем ошибаться. А пока не слишком нам доверяйте».

Наконец настало время объявить БОЛЬШОЙ КОНКУРС ЧИПА 1987 ГОДА. Как и в прошлом году, победителей ждут КАЛЬКУЛЯТОРЫ.

Условия конкурса:

1. Написать любую программу для калькулятора. Если его нет, то написать программу-сказку, как раньше. Выигрывает тот, у кого самая интереснаяпрограмма.

2. Предложить идею электронной игры. Здесь программа не нужна, будет цениться оригинальность и фантазия.

3. Шутливый конкурс «Кто самый средний?». Назовите год, месяц, число и час своего рождения (не знаете час – придумайте). Выиграет тот, чья дата окажется ближе всех к среднему значению. Вам не надо считать среднее, это мы сделаем сами, вы просто пришлите год, месяц, число и час своего рождения.

На конверте укажите девиз: «БОЛЬШОЙ КОНКУРС ЧИПА 1987 ГОДА». Ответы отправлять не позднее 1 февраля 1988 года.

Как обхитрить Мегафлопа

– Слушай, Сережа, а ты здорово вырос за последний год, – сказал Чип, одновременно для разминки перемножая десятизначные числа. Он вообще никогда не сидел спокойно – говорил фразу и, пока Сережа думал над ответом, успевал решить про себя какую-нибудь задачу. Потом быстро обдумывал Сережины слова, отвечал и снова погружался в расчеты. Однако его собеседник ничего не замечал – так быстро Чип думал.

Чип говорил, что Сережа был для него медленным внешним устройством, а расчет шел в фоновом режиме. То есть на фоне расчета он разговаривал с Сережей, как солист в опере поет на фоне оркестра. Например, ЭВМ может одновременно печатать на машинке и решать сложную задачу. Пока машинка печатает строку, Чип успевает сделать массу вычислений. Потом он прервет решение задачи, пошлет в печать новую строку и возобновит работу с того места, где остановился. Иначе Чипу пришлось бы очень долго, по его понятиям, сидеть без дела, а машины этого не любят. Поэтому в хороших вычислительных машинах могут одновременно решаться десятки проблем, и одна программа не замечает присутствия остальных.

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

– Да. на целых пять сантиметров. А ты почему не растешь? Когда ты станешь таким же большим, как твой папа – Центральный процессор?

– Мы, чипы, не растем, а сразу рождаемся взрослыми: большими или маленькими, умными или глупыми, быстрыми или медленными. Но бывает так, что несколько медленных чипов оказываются быстрее одного быстрого.

– Десять черепах обгоняют одного зайца?

– Почти так, но поскольку машины сами думать не умеют, им должен помочь хороший программист. Вот как-то раз приехал к нам из-за границы нахальный чип Мегафлоп. Был он маленький, гладкий и все ходил и похвалялся: «Эх вы, старикашки! Вам бы на пенсию или в демонтаж! Краска облуплена, час поработаете и перегреваетесь, а уж считаете вы совсем как черепахи. Пока вы два числа сложите, я – сто, пока вы два числа умножите, я – двести. На что вы годны?!» Обидно нам стало, и решили мы пойти к программисту Лене и попросить помощи – неужто и правда нами можно только гвозди забивать?

Леня засмеялся и сказал: «Чипы! Решите-ка такую задачу: по длинной улице идут сплошным потоком машины. Между каждой парой машин может проскочить один человек. За какое время перейдет на другую сторону улицы рота солдат, если один человек перебегает улицу за десять секунд?». «За тысячу секунд», – хором ответили чипы. «Ну и неверно! Кто вам мешает построить солдат вдоль улицы, и тогда вся рота перейдет за десять секунд.

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

– Погоди-ка, – перебил Чипа Сережа. – Ведь тысяча – это не степень двойки. Разделил пополам – 500, сложил 500 пар, разделил на 250 пар, снова попарно сложил, разделил на 125 пар, сложил – и стоп! Дальше не делится! Не додумал твой Леня алгоритм.

– Молодец, – усмехнулся Чип, – не зря я тебя учил. Что же, в этом случае проще всего добавить три числа, равных нулю.

– А зачем нули добавлять?

– Чтобы всем чипам работа досталась. Сумма не изменится, а слагаемых станет 128, их можно до конца разбивать на пары. А еще проще, как только количество чисел становится нечетным, к ним добавляется еще одно число, равное нулю.

– Удивительно! Вроде лишнюю работу делаем, а получается быстрее.

– Зато все чипы при деле, в ногу шагают! – Чип подмигнул Сереже и продолжил: – Так мы и сделали, а потом и сами предложили Мегафлопу вторую задачу: найти наибольшее из тысячи чисел. (Кстати, как это сделать за десять шагов?) Потом третью: вывести оценки за четверть для всей школы (для каждого ученика его оценка за четверть по каждому предмету есть среднее арифметическое его оценок, полученных в течение четверти). Как, по-твоему, мы решили эту задачу?

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

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

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

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

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