§ 1.1. Конструирование алгоритмов

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

Первый способ называют разработкой «сверху вниз», или методом пошаговой детализации; говорят также о последовательном уточнении. Второй — разработкой «снизу вверх». Разберём оба, но подробно — первый: именно им пользуются, когда задача новая и готовых кусков под неё нет.

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

Начинают с удобной выдумки. Вообразим исполнителя, которому доступно вообще всё: он поймёт любое поручение и выполнит его безошибочно. Такому достаточно одной команды — «реши задачу», и остаётся только назвать, что дано и что требуется получить. Выходит совсем короткий линейный алгоритм: начало, ввод исходных данных, единственное предписание с постановкой задачи, вывод результата, конец.

Настоящий исполнитель, конечно, ничего подобного не умеет. Тогда это единственное предписание расписывают подробнее. Задачу делят на несколько частей попроще; решение каждой части записывают отдельной командой — и не смущаются, если новые команды по-прежнему исполнителю не по силам. С каждой непонятной командой поступают точно так же ещё раз и ещё, пока в записи не останется ничего, чего исполнитель не умеет. Затем полученные команды выстраивают в нужном порядке — это и есть искомый алгоритм.

Разработка «снизу вверх» устроена наоборот. Сначала готовят библиотеку: набор небольших самостоятельных алгоритмов, которые пригодятся не в одной задаче, а в целом их классе. Скажем, выбрать большее из двух чисел, обменять значения двух переменных, нарисовать правильный многоугольник. И только потом пишут основной алгоритм — он обращается к кускам библиотеки, как к собственным командам.

Разберём пошаговую детализацию на исполнителе Робот. Робот живёт на клетчатом поле, между соседними клетками кое-где стоят стены. Двигают его четыре команды: влево, вправо, вверх и вниз — каждая переводит Робота в соседнюю клетку, а если там стена, Робот разрушается. Команда закрасить закрашивает клетку, в которой он стоит. Условия сообщают об обстановке вокруг: слева свободно, справа свободно, сверху свободно, снизу свободно истинны, когда стены с этой стороны нет; парные им слева стена, справа стена, сверху стена, снизу стена — наоборот. Отдельно проверяется условие клетка закрашена. Условия соединяют словами и, или, не; ветвление записывают как «если … то … иначе … все», цикл — как «нц пока … кц».

Задача. Робот стоит где-то внутри вертикального коридора: слева и справа тянутся стены, сверху и снизу коридор открыт, ни одна клетка не закрашена. Нужно закрасить все клетки коридора и вернуть Робота туда, откуда он начал. Длина коридора неизвестна, известно только, что она конечна.

Писать команды пока рано. Сначала опишем замысел крупными частями — модулями: 1) закрасить клетки, лежащие выше исходной; 2) вернуться в исходную клетку; 3) закрасить клетки, лежащие ниже исходной; 4) вернуться в исходную клетку; 5) закрасить исходную клетку. Ни один из пяти модулей Роботу пока не по зубам — значит, каждый предстоит уточнить.

Модуль 1. Шагнём вверх и, пока по бокам стоят стены (а это и значит «мы ещё в коридоре»), будем закрашивать клетку и подниматься. Цикл прекратится сам, когда Робот окажется над верхним краем коридора: там стен по бокам уже нет.

вверх нц пока слева стена и справа стена закрасить вверх кц

Модуль 2. Командой вниз вернём Робота в коридор. Все клетки выше исходной уже закрашены, а сама исходная — ещё нет. Значит, достаточно спускаться, пока клетка под Роботом закрашена; на первой незакрашенной он и остановится — это его старт.

вниз нц пока клетка закрашена вниз кц

Модули 3 и 4 — зеркальные близнецы первых двух: та же работа, только вниз. Модуль 5 состоит из одной команды закрасить.