Пионер 1988-06, страница 28

— Чип, а как поживает электронный Мальчик с пальчик? — спросил Сережа.— Расскажи мне про него еще какую-нибудь историю!

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

— Согласен,— обрадовался Сережа.— Начинай!

«Итак, как-то ночью, когда все инженеры спали, в электрическую сеть прокрался страшный Скачок Напряжения и напал на чипов. Сам Мальчик с пальчик почти не пострадал, его спасли друзья — предохранители, а вот у его старшего брата сгорела вся оперативная память. Жалко стало Мальчику с пальчик братца — теперь тому прямая дорога в демонтаж. И решил он пойти на поклон к великану Гигабайту: ему что проглотить, что отдать пару килобайт— раз плюнуть.

Мама с папой стали Мальчика с пальчик отговаривать:

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

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

Взял он узелок, положил туда пару батареек и отправился в путь. Долго ли. коротко плутал по лабиринту, но наконец нашел Гигабайта. Увидел его великан, разинул пасть...»

— Постой, постой.— перебил Чипа Сережа,— это мне напоминает историю про Тесея и Минотавра, я ее читал в «Легендах и мифах Древней Греции». Только ты забыл про Ариадну, которая дала Тесею моток ниток. Он привязал один конец у входа, а потом, когда убил злого Минотавра, по нитке нашел дорогу назад.

В ПОИСКАХ ВЫХОДА

— Молодец,— похвалил Чип Сережу,— как раз в нитке все и дело. Герою Тесею, который хорошо умел только махать мечом, нитка действительно была необходима. А наш электронный Мальчик с пальчик выйдет из лабиринта без всякой нитки. Так что это не совсем та же история.

— Извини, Чип,— спохватился Сережа,— рассказывай дальше.

«— А, это ты, малявка — загрохотал великан,— зачем пожаловал? Тебя съесть— только аппетит раздразнить.

— Будь добр, дай мне пару килобайт оперативной памяти вылечить братца. Для тебя это мелочь, а ему без них один путь — на свалку.

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

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

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

— Алгоритм очень прост, называется «Правило правой руки». Смотри: я кладу мой узе-

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

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

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

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