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

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

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

Далее, если исполнитель уже может выполнить данный алгоритм в рамках его системы команд, то алгоритм задают исполнителю именно в таком виде. Если же нет – алгоритм разбивают на несколько команд, каждая из которых проще основного алгоритма. Если какие-то из команд алгоритма выходят за рамки системы команд исполнителя их тоже разбивают на более простые. Так происходит до тех пор, пока все команды алгоритма не входят в систему команд исполнителя.

После этого нам остаётся объединить все команды и предписания в определённом порядке. Составить из них алгоритм.

Для примера разработаем алгоритм для нахождения среднего арифметического последовательности чисел. Вспомним, что средним арифметическим нескольких чисел называется их сумма, поделённая на их количество.

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

Алгоритм нахождения суммы элементов массива мы уже знаем и можем записать. Разделить эту сумму на количество элементов тоже не составляет никакого труда. Нужно лишь объединить алгоритмы решения данных подзадач.

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

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

Также можно задать и циклически алгоритм. При его записи сначала идут служебные слова «нц» и «пока», а после них записывается одно из условий. Ниже записывается последовательность команд, которая будет повторяться, пока условие выполняется. Заканчивается оператор цикла служебным словом «кц»

Исполнитель «Робот» может использовать простые условия:

·     сверху стена;

·     снизу стена;

·     справа стена;

·     слева стена;

·     сверху свободно;

·     снизу свободно;

·     справа свободно;

·     слева свободно;

·     клетка закрашена.

Из них можно делать составные условия, используя логические операции «И», «ИЛИ» и «НЕ».

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

Очевидно, что общую задачу «Закрасить все угловые клетки» можно разбить на более простые подзадачи:

1.  Переместиться в левую верхнюю клетку.

2.  Закрасить.

3.  Переместиться в правую верхнюю клетку.

4.  Закрасить.

5.  Переместиться в правую нижнюю клетку.

6.  Закрасить.

7.  Переместиться в левую нижнюю клетку.

8.  Закрасить.

Обратим внимание что подзадачи по закраске клеток уже соответствуют системе команд исполнителя «Робот», а значит, дальнейшее их упрощение не требуется. А подзадачи, связанные с перемещением, ещё нужно уточнить.

Подзадачу «Переместиться в левую верхнюю клетку» можно разбить на две подзадачи. «Переместиться в верхний ряд» и «Переместиться в левый ряд», которые можно перефразировать в соответственно «пока сверху свободно – вверх» и «пока слева свободно – влево». Это уже соответствует системе команд Робота. Обратим внимание, что эти две подзадачи могут быть выполнены в другом порядке, сначала мы можем переместиться в левый ряд, а затем в верхний. Все равно мы окажемся в левой верхней клетке.

Подзадачу «Переместиться в правую верхнюю клетку» можно так же разбить на две подзадачи «Переместиться в верхний ряд» и «Переместиться в правый ряд», но обратим внимание, что перед этим мы закрасили левую верхнюю клетку, следовательно, Робот уже в верхнем ряду и первую подзадачу выполнять не нужно. Остаётся лишь подзадача «Переместиться в правый ряд», её можно перефразировать «Пока справа свободно – вправо», что соответствует системе команд исполнителя.

Подзадачу «Переместиться в правую нижнюю клетку», можно разбить на подзадачи: «Переместиться в правый ряд» и «Переместится в нижний ряд». Но так, как до этого мы закрасили правую верхнюю клетку – то Робот уже в правом ряду, и остаётся только «Переместиться в нижний ряд», что можно перефразировать «Пока снизу свободно – вниз», что соответствует системе команд Робота.

Таким же образом подзадача «Переместиться в левую нижнюю клетку» преобразуется в команду «Пока слева свободно – влево».

Схема алгоритма решения задачи

Обратим внимание, что если мы будем закрашивать клетки в другом порядке, то изменится и порядок решения подзадач. Теперь нам остаётся лишь собрать последовательность команд воедино, записать алгоритм для Робота и протестировать его.

Итак, в начале нам нужно записать цикл «пока сверху свободно», внутри которого будет одна команда – «вверх». Затем цикл «пока слева свободно», содержащий команду «влево». После данного цикла нам нужно закрасить клетку. Далее последует цикл «Пока справа свободно», содержащий команду «вправо», после чего снова закрасим клетку. Теперь запишем цикл «пока снизу свободно», в котором будет команда «вниз», и снова закрасим клетку. И наконец, запишем цикл «пока слева свободно», который будет содержать команду «влево», после чего закрасим клетку.

Алгоритм решения задачи

Ожидаемым результатом будут закрашенные угловые клетки. Запустим программу на выполнение. Убедимся, что фактический результат соответствует ожидаемому, а значит – задача решена верно.

Результат работы программы

Важно запомнить:

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