Игры с Чипом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРОГРАММА: «НАЙТИ ВЫХОД».

1. Возьмись правой рукой за стену.

2. Положи узелок у этой стены.

3. Иди по правилу «правой руки» (ситуация).

4. ЕСЛИ ситуация-выход, ТО КОНЕЦ.

ИНАЧЕ:

((5. Возьми узелок.

6. Иди вдоль правой стены до первой развилки.

7. Войди во второй справа коридор.

8. Вернись ко второму пункту программы.))

ПОДПРОГРАММА «ИДИ ПО ПРАВИЛУ» ПРАВОЙ РУКИ» (ситуация).

1. Иди вдоль правой стены до развилки.

2. ЕСЛИ увидел узелок у правой стены, ТО

((ситуация-цикл

ВОЗВРАТ)).

3. Выбери самый правый коридор.

4. ЕСЛИ выход, ТО

((ситуация-выход

ВОЗВРАТ)).

5. Выполняй первый пункт подпрограммы.

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