Первая премудрость, которую надо усвоить (мы о ней в предыдущей беседе упоминали), — это то, что каждое действие ЭВМ выполняется по команде, команды пронумерованы и, если нет других указаний, выполняются в порядке своих номеров. Точно так же, как в обычной очереди. Подобный порядок выполнения команд называется их естественной последовательностью. Выполнение команд в их естественной последовательности (если, еще раз повторяем, нет других указаний) можно назвать основным законом функционирования ЭВМ.
Ну а теперь в путь по лабиринту. Раз-два, раз-два, левой-правой, левой-правой! Первая команда, вторая команда, третья команда, четвертая команда, топ-топ, топ-топ! Да простит нам читатель это сюсюканье — не забывайте, что мы имеем дело с новорожденной ЭВМ.
Движемся по коридору лабиринта. Искушенный читатель мог бы сделать здесь и, наверное, сделает по меньшей мере два возражения. Первое, по его мнению, это то, что двигаться по плоскости (считаем лабиринт плоским) — это значит каждый раз вычислять координаты очередной точки. Следовательно, машина все-таки вычислительная? Все в конечном итоге сводится к вычислениям?
Ничего подобного! С той же легкостью, как с арифметическими операциями, машина оперирует и с отношениями, в частности с отношениями смежности. В таких условиях двигаться — это значит освобождать некоторый элемент площади (записывать в него нуль, если раньше была записана единица) и занимать соседний, смежный, элемент — заменять в нем нуль на единицу. Что такое «соседний», машина, как мы только что сказали, знает.
Второе возражение более серьезное. К чему оно сводится? По условию, движение совершается в лабиринте и перешагивать через стенки нельзя. Поэтому каждый шаг представляет собой не элементарное действие, а целую последовательность действий такого типа: ткнулись направо — уперлись в стенку, изменили направление движения — снова уперлись в стенку и так далее, пока впереди не обнаруживается свободное пространство и можно делать шаг.
Топ-топ, левой-правой! Выполняется естественная последовательность команд. Но вот обнаруживается разветвление коридоров. По какому из двух путей продолжать движение? Для выбора есть много способов.
Простейший — всегда поворачивать, например, только вправо. Точнее, в самый правый из нескольких коридоров при условии, что он уже однажды не был пройден.
Можно бросить монету. Да-да, бросить монету! Иначе говоря, совершить случайный выбор. Случайный выбор машина умеет делать гораздо лучше человека, и это подтверждается тем, что в орел и решку машина у человека всегда выигрывает.
Можно вычислить вероятность успеха для каждого из путей.
Наконец, можно заглянуть в память (машинную, конечно) и воспользоваться предыдущим опытом.
Но что важно? Все сказанное не имеет никакого отношения к программированию. Программист должен знать одно: попадая в точку разветвления, машина должна выбрать путь. Как она будет это делать, относится не к программе, а к существу задачи. Попутно выполняется небольшая проверка. Не достигнут ли конец лабиринта? Если достигнут, то машина, ликуя, сообщает о выполнении задания, если нет, она возвращается в исходную точку программы и все начинается сначала: топ-топ, левой-правой…
Рис. 8.
Вот и вся премудрость. Давайте рассмотрим внимательно рисунок 8. Начнем с самого верха, где написано: «Вход в программу». Логичнее было бы написать «начало», но дело в том, что относительно каждой программы трудно определить, где у нее начало. Каждая программа может быть частью другой, более сложной. Слова «Вход в программу» и означают, что, начиная с определенного момента, действует именно эта программа. Кроме того, здесь возможно выполнение некоторых вспомогательных действий, которые на данном уровне рассмотрения несущественны.
Вошли в программу. Минуем пока прямоугольник, на котором написано «Модификация», и обращаемся к прямоугольнику «Тело программы». Тело программы — это и есть цепочка команд, выполняемых в их естественной последовательности. Какие это команды, совершенно безразлично. Потому мы и выбрали в качестве примера отыскание пути в лабиринте, что эта задача напоминает другие, подчас гораздо более серьезные, например решение вопроса о том, увольнять или не увольнять некоторого сотрудника.
Тело программы предусматривает, кроме команд, наличие операндов, то есть объектов, над которыми выполняются команды. Операндом может быть все, что угодно. В нашем случае это элементы площади коридоров с пометками о том, заняты они или свободны, были однажды пройдены или нет. Каждый такой элемент содержит в себе список соседних элементов. Но все это не имеет никакого отношения к программированию. Программисту достаточно знать, что операнды существуют. Операнды, как и команды, нумеруются по порядку, причем порядковый номер операнда называется его адресом. В состав каждой команды входит адрес соответствующего операнда.