Игры с Чипом - [31]

— Ха-ха-ха, мелюзга, да если я тебе даже дам пару килобайт, все равно из лабиринта не выберешься. Я и сам не знаю, как отсюда выйти.

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

— Ну-ка, расскажи свой алгоритм, — заинтересовался Гигабайт, — а потом прогуляемся вместе наружу. Если выберемся — подарю тебе не два килобайта, а целых десять.

— Алгоритм очень прост, называется «Правило правой руки». Смотри: я кладу мой узелок и иду вперед вдоль правой стены. Как только встречаю развилку, поворачиваю направо. При таком алгоритме я не могу зациклиться — начать ходить по кругу, потому что, если бы я начал ходить по кругу, это бы говорило о том, что я выбирал все время не самый правый коридор. — И Мальчик с пальчик начертил на песке такой рисунок (рис. 1). — Поэтому правильный обход дал бы следующий результат (рис. 2)».

— Постой, — опять не выдержал Сережа, — а если сразу справа от тебя вот такой замкнутый коридор (рис. 3), то ты зациклишься!

— Ты невнимательно слушал. Мальчик с пальчик ясно сказал: «Кладу мой узелок». Ведь если у лабиринта нет выхода, алгоритм тоже не приведет к успеху, поэтому он и уточнил: «Раз я сюда пришел, то хоть один выход есть» (рис. 4). Поэтому, наткнувшись на свой узелок, он поступит следующим образом: возьмет его, у ближайшей развилки выберет не самый правый, а второй справа коридор (рис. 5), ведь из развилки может быть много выходов, и повторит тот же алгоритм: положит узелок, пойдет вдоль правой стенки и так далее. Можно доказать, что если выход есть, то мы его обязательно найдем. А теперь попробуй написать программу выхода из лабиринта.

Вот что после некоторого раздумья написал Сережа:

ПРОГРАММА: «НАЙТИ ВЫХОД».
1. Возьмись правой рукой за стену.
2. Положи узелок у этой стены.
3. Иди по правилу «правой руки» (ситуация).
4. ЕСЛИ ситуация-выход, ТО КОНЕЦ.
ИНАЧЕ:
((5. Возьми узелок.
6. Иди вдоль правой стены до первой развилки.
7. Войди во второй справа коридор.
8. Вернись ко второму пункту программы.))

ПОДПРОГРАММА «ИДИ ПО ПРАВИЛУ» ПРАВОЙ РУКИ» (ситуация).
1. Иди вдоль правой стены до развилки.
2. ЕСЛИ увидел узелок у правой стены, ТО
((ситуация-цикл
ВОЗВРАТ)).
3. Выбери самый правый коридор.
4. ЕСЛИ выход, ТО
((ситуация-выход
ВОЗВРАТ)).
5. Выполняй первый пункт подпрограммы.

— Хорошо, — сказал Чип, — а теперь давай попробуем применить твою программу. Вот в журнале «Веселые картинки» напечатан лабиринт. Давай поищем путь от крота к мышке.

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

ОТ РЕДАКЦИИ:

Ребята! Проверьте Сережину программу на других лабиринтах. А если лабиринтов под рукой не найдется, придумайте их сами и пришлите нам. Любителям трудных задач мы предлагаем сочинить программу, которая сама будет строить лабиринты. На конверте напишите девиз: «ЛАБИРИНТ».

Секретное послание

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

— Знаешь, Чип, обиднее всего, что так много ребят прислали чужие программы, вместо того чтобы придумать свои.

— Да, стыдно! — Чип усмехнулся и добавил: — А ведь пройдет лет пять — и появятся компьютеры пятого поколения, которые смогут сами писать программы. Эти ребята рискуют остаться без работы в двадцать первом веке.

— Ну вот смотри, Чип. Витя Лавренко из г. Истры придумал свою игру «рыбная ловля». Идея, по-моему, интересная. Можно выбрать наживку, удочку, место, где лучше клюет, рыба может и оборвать леску, ее видно сквозь воду, так что игра азартная.

— А мне больше нравится игра «автогонки» Вити Урнышева из Петропавловска-Камчатского. У него гонщик перед началом гонки сам собирает автомобиль. Сам выбирает мотор, кузов, колеса... Интересные работы прислали Миша Погонин из Архангельска, Саша Бауров из Новосибирска, Карапет Овивян из Москвы, Петя Сурдяев из Одессы и Паша Юркин из с. Громово.

— Нет, Чип, так мы не выберем победителя. Слушай, а может, возьмем самого среднего — это же тоже одно из условий конкурса?

— Давай смотреть: средний участник конкурса-87 родился 17 августа 1975 года в 5 часов 30 минут. Ближе всех к этому моменту Олеся Матвеева из Армавира, она родилась в этот день, но на час позже. Правда, в остальном ее работа намного слабее семи лучших.

— Опять несправедливо, — возразил Сережа, — все-таки у двух Вить работы интереснее. Знаешь, а что если дать им, семи финалистам, еще одно задание. Кто лучше справится, тот и победит. Чип, помоги придумать такую задачу!