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