Беседы об информатике

Движемся по коридору лабиринта. Искушенный читатель мог бы сделать здесь и, наверное, сделает по меньшей мере два возражения. Первое, по его мнению, это то, что двигаться по плоскости (считаем лабиринт плоским) — это значит каждый раз вычислять координаты очередной точки. Следовательно, машина все-таки вычислительная? Все в конечном итоге сводится к вычислениям?

Ничего подобного! С той же легкостью, как с арифметическими операциями, машина оперирует и с отношениями, в частности с отношениями смежности. В таких условиях двигаться — это значит освобождать некоторый элемент площади (записывать в него нуль, если раньше была записана единица) и занимать соседний, смежный, элемент — заменять в нем нуль на единицу. Что такое «соседний», машина, как мы только что сказали, знает.

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

Топ-топ, левой-правой! Выполняется естественная последовательность команд. Но вот обнаруживается разветвление коридоров. По какому из двух путей продолжать движение? Для выбора есть много способов.

Простейший — всегда поворачивать, например, только вправо. Точнее, в самый правый из нескольких коридоров при условии, что он уже однажды не был пройден.

Можно бросить монету. Да-да, бросить монету! Иначе говоря, совершить случайный выбор. Случайный выбор машина умеет делать гораздо лучше человека, и это подтверждается тем, что в орел и решку машина у человека всегда выигрывает.

Можно вычислить вероятность успеха для каждого из путей.

Наконец, можно заглянуть в память (машинную, конечно) и воспользоваться предыдущим опытом.

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

Рис. 8.

Вот и вся премудрость. Давайте рассмотрим внимательно рисунок 8. Начнем с самого верха, где написано: «Вход в программу». Логичнее было бы написать «начало», но дело в том, что относительно каждой программы трудно определить, где у нее начало. Каждая программа может быть частью другой, более сложной. Слова «Вход в программу» и означают, что, начиная с определенного момента, действует именно эта программа. Кроме того, здесь возможно выполнение некоторых вспомогательных действий, которые на данном уровне рассмотрения несущественны.

Вошли в программу. Минуем пока прямоугольник, на котором написано «Модификация», и обращаемся к прямоугольнику «Тело программы». Тело программы — это и есть цепочка команд, выполняемых в их естественной последовательности. Какие это команды, совершенно безразлично. Потому мы и выбрали в качестве примера отыскание пути в лабиринте, что эта задача напоминает другие, подчас гораздо более серьезные, например решение вопроса о том, увольнять или не увольнять некоторого сотрудника.

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

Дойдя до конца естественной последовательности, переходим в следующий прямоугольник, обозначенный как «формулирование условий». Здесь происходит следующее. Последовательно, позиция за позицией, просматривается список элементов площади, смежных с данным. Возможны три случая. Во-первых, в списке оказывается лишь один смежный элемент, причем этот единственный элемент либо уже пройден, либо еще не пройден. Во-вторых, в списке имеются два или более смежных элементов. В-третьих, единственный смежный элемент оказывается выходом из лабиринта.

При всех условиях из прямоугольника «Формулирование условий» мы переходим в ромб, на котором написано: «Принятие решения» (почему ромб, мы не знаем — такова общепринятая символика у программистов). В нашем случае ромб эквивалентен вопросу: является ли смежный элемент выходом из лабиринта? Если ответ положительный (на рис. 8 так и написано, «да»), работа программы заканчивается.