— На это тебе не хватило бы даже летних каникул, — засмеялся Чип. — Только на конкурс
— Все правильно, — сказал Чип, проверив программу, — только ты ведь не знаешь, сколько в мешке писем. Поэтому лучше будет, если ты напишешь третью строчку программы так:
И еще хорошо бы вставить в блок между четвертой и пятой строчками строку:
— По-моему, — сказал Сережа, — все трое допустили небольшую ошибку. Чтобы выйти из трясины, нам надо найти не брата, стоящего выше всех, а место, которое выше, чем то, где забит колышек. Возможно, что одна веревка будет выше других, но все братья будут находиться ниже колышка. Тогда мы не только не выйдем из трясины, но, наоборот, завязнем еще глубже. Программу «Выбери верхнего» я бы написал так:
— Правильно, Сережа, я бы даже усилил твое утверждение и написал: «Если есть хоть одна, идущая не вниз» — зачем ждать утра, если есть возможность испробовать еще один вариант, оставаясь на том же уровне.
— Посмотри, Чип, вот сюжеты электронных игр, целых семьдесят писем.
— С этим заданием лучше всех справились Никита ЛИТВИНЕНКО, Краснокаменск и Ира РЯБЫХ, п. Ларба. Пятиклассник Никита предложил игру «Леопольд, выходи!» и даже нарисовал картинку. Сюжет игры такой: две мыши, которыми управляют с помощью клавиш компьютера, дразнят кота Леопольда и прыгают через кнопки, лежащие на дороге. Если мышка приземлится на кнопку, раздается громко «Ай!» (современные компьютеры уже умеют разговаривать), и игрок получает штрафное очко. Дорога с кнопками может двигаться быстрее или медленнее. Поскольку мышек две и они прыгают независимо друг от друга, управлять ими будет не просто, такая игра потребует хорошей координации движений и быстрой реакции.
— Чип, а помнишь того сердитого читателя из Свалявы? Он писал, что мы даем слишком простые задачи. Ему предложили более трудное задание и попросили написать на конверте: «Чип, это я».
— Конечно, помню. Письма из Свалявы мы, правда, пока не получили, зато вон лежат семь писем из разных уголков страны с надписью «Чип, это я». Не знаю, что хотели сказать их авторы, но, к сожалению, в этих письмах нет ни слова о сложном задании, просто ответы на конкурс «Турнир». Кстати, с этим конкурсом справились многие ребята. Правильные ответы прислали Дима АНТОНОВ, Пермь. Ярослав ВЕРБЕ, Киев; Паша ДАНИЛОВ, Загорск; Юра ДУКАЧ, Экибастуз; Саша ЕЛЕСЕЕВ, Ростов-на-Дону; Алексей ЕРОХИН, Марганец; Дима ЗАЙЦЕВ, Апатиты; Кирилл ИЛЬИН, Ленинград; Саша КОНЕВ, Курчатов; Сергей КОРОВЯКОВСКИЙ, Мурманск; Роман КАЛИНА, Оренбург; Таня КРЕСТОВСКИХ, Ухта; Лена МАТАШКОВА, Витебск; Слава НИКОЛАЕВ, с Новомихайловское; Игорь ПЕРМИНОВ. г. Ступино; Алеша МАЛЬКОВ, г. Шимановск; Ольга Л., с. Вихоревка; С. РАССТРИГИН, Рязань; Юра ПЕТРАШОВ, Тольятти; Женя СЕРГУНОВ, Юрга; Дима СУТОРИН, Пермь; Яна СУХОРУКОВА, Красноярск; Оля СИЛИНА, Юрьев-Польский; Ольга ШЕПТАЛИНА, Балашиха; Эльвина ЮНУСОВА, Уфа.
Много программ на бейсике, программ для микрокалькуляторов прислали наши читатели на задание «Турнир». Больше всех постарался Станислав Расстригин: он прислал программы на трех языках — бейсике, алголе и рапире. Игорь Перминов из Ступина на базе нашего задания придумал сюжет электронной игры «Турнир».
— Чип, а давай предложим тем читателям, кто занимается в кружках программирования, усложнять для себя наши задания. Пусть записывают программы на машинных языках или придумывают на основе этих программ электронные игры.
— Конечно, если наши задания кому-то кажутся слишком простыми, их надо использовать как отправную точку для самостоятельной работы.
В поисках выхода
— Чип, а как поживает электронный Мальчик с пальчик? — спросил Сережа. — Расскажи мне про него еще какую-нибудь историю!
— Ладно, — ответил Чип, — только я буду рассказывать, а ты писать программы. Согласен?
— Согласен. — обрадовался Сережа. — Начинай!
— Итак, как-то ночью, когда все инженеры спали, в электрическую сеть прокрался страшный Скачок Напряжения и напал на чипов. Сам Мальчик с пальчик почти не пострадал, его спасли друзья — предохранители, а вот у его старшего брата сгорела вся оперативная память. Жалко стало Мальчику с пальчик братца — теперь тому прямая дорога в демонтаж. И решил он пойти на поклон к великану Гигабайту: ему что проглотить, что отдать пару килобайт — раз плюнуть.
Мама с папой стали Мальчика с пальчик отговаривать:
— Не ходи — и брату не поможешь, и сам пропадешь. Построил себе Гигабайт из каналов и контролеров страшный лабиринт. Кто в этот лабиринт заходит, того великан съедает, а если и не съест тебя Гигабайт, то все равно заблудишься, закружишься в бесконечном цикле, не найдешь обратной дороги.
— Ничего, — отвечает Мальчик с пальчик, — мы с Гигабайтом старые знакомые, один раз я его уговорил, уговорю и в другой.
Взял он узелок, положил туда пару батареек и отправился в путь. Долго ли, коротко плутал по лабиринту, но наконец нашел Гигабайта. Увидел его великан, разинул пасть...»
— Постой, постой. — перебил Чипа Сережа, — это мне напоминает историю про Тесея и Минотавра, я ее читал в «Легендах и мифах Древней Греции». Только ты забыл про Ариадну, которая дала Тесею моток ниток. Он привязал один конец у входа, а потом, когда убил злого Минотавра, по нитке нашел дорогу назад.
— Молодец, — похвалил Чип Сережу, — как раз в нитке все и дело. Герою Тесею, который хорошо умел только махать мечом, нитка действительно была необходима. А наш электронный Мальчик с пальчик выйдет из лабиринта без всякой нитки. Так что это не совсем та же история.
— Извини, Чип, — спохватился Сережа, — рассказывай дальше.
«— А, это ты, малявка, — загрохотал великан, — зачем пожаловал? Тебя съесть — только аппетит раздразнить.
— Будь добр, дай мне пару килобайт оперативной памяти вылечить братца. Для тебя это мелочь, а ему без них один путь — на свалку.
— Ха-ха-ха, мелюзга, да если я тебе даже дам пару килобайт, все равно из лабиринта не выберешься. Я и сам не знаю, как отсюда выйти.
— А вот и выйду, — засмеялся Мальчик с пальчик. — Я знаю алгоритм выхода из любого конечного плоского лабиринта. Раз я сюда пришел, то хоть один выход из твоего лабиринта есть, так что можешь обо мне не беспокоиться, дорогу я найду.
— Ну-ка, расскажи свой алгоритм, — заинтересовался Гигабайт, — а потом прогуляемся вместе наружу. Если выберемся — подарю тебе не два килобайта, а целых десять.
— Алгоритм очень прост, называется «Правило правой руки». Смотри: я кладу мой узелок и иду вперед вдоль правой стены. Как только встречаю развилку, поворачиваю направо. При таком алгоритме я не могу зациклиться — начать ходить по кругу, потому что, если бы я начал ходить по кругу, это бы говорило о том, что я выбирал все время не самый правый коридор. — И Мальчик с пальчик начертил на песке такой рисунок (рис. 1). — Поэтому правильный обход дал бы следующий результат (рис. 2)».
— Постой, — опять не выдержал Сережа, — а если сразу справа от тебя вот такой замкнутый коридор (рис. 3), то ты зациклишься!
— Ты невнимательно слушал. Мальчик с пальчик ясно сказал: «Кладу мой узелок». Ведь если у лабиринта нет выхода, алгоритм тоже не приведет к успеху, поэтому он и уточнил: «Раз я сюда пришел, то хоть один выход есть» (рис. 4). Поэтому, наткнувшись на свой узелок, он поступит следующим образом: возьмет его, у ближайшей развилки выберет не самый правый, а второй справа коридор (рис. 5), ведь из развилки может быть много выходов, и повторит тот же алгоритм: положит узелок, пойдет вдоль правой стенки и так далее. Можно доказать, что если выход есть, то мы его обязательно найдем. А теперь попробуй написать программу выхода из лабиринта.
Вот что после некоторого раздумья написал Сережа:
— Хорошо, — сказал Чип, — а теперь давай попробуем применить твою программу. Вот в журнале «Веселые картинки» напечатан лабиринт. Давай поищем путь от крота к мышке.
Вот по какому пути шли Сережа с Чипом. Если смотреть сверху, то путь может показаться не самым коротким: зачем обходить явные тупики и заворачивать во все закоулки? Но зато этот путь они прошли, как бы находясь в лабиринте, двигаясь ощупью в полной темноте, и все-таки выбрались наружу.
ОТ РЕДАКЦИИ:
Ребята! Проверьте Сережину программу на других лабиринтах. А если лабиринтов под рукой не найдется, придумайте их сами и пришлите нам. Любителям трудных задач мы предлагаем сочинить программу, которая сама будет строить лабиринты. На конверте напишите девиз: «ЛАБИРИНТ».
Секретное послание
Сережа с Чипом долго спорили, подводя итоги Большого конкурса 1987 года. Они отобрали семь лучших работ, и в каждой были интересные идеи, но, увы, ни в одной не было такого блеска, как в работах победителей прошлого года. Да и самих писем получено меньше. Тогда две с половиной тысячи, а сейчас 615. Конечно, сказки и шутки программировать легче, чем серьезные задачи.
— Знаешь, Чип, обиднее всего, что так много ребят прислали чужие программы, вместо того чтобы придумать свои.
— Да, стыдно! — Чип усмехнулся и добавил: — А ведь пройдет лет пять — и появятся компьютеры пятого поколения, которые смогут сами писать программы. Эти ребята рискуют остаться без работы в двадцать первом веке.
— Ну вот смотри, Чип. Витя Лавренко из г. Истры придумал свою игру «рыбная ловля». Идея, по-моему, интересная. Можно выбрать наживку, удочку, место, где лучше клюет, рыба может и оборвать леску, ее видно сквозь воду, так что игра азартная.