Урок №15. Разбиение задачи на подзадачи. Составление алгоритмов и программ с использование ветвлений, циклов и вспомогательных алгоритмов.
В 8 классе вы познакомились с базовыми алгоритмическими конструкциями (следованием, ветвлением, циклом), научились записывать несложные алгоритмы для формальных исполнителей и на одном из языков программирования.
При конструировании (разработке) алгоритма решения сложной задачи её принято разбивать на более простые подзадачи. При этом, как правило, используется один из следующих методов:
- метод разработки «сверху вниз»;
- метод разработки «снизу вверх».
Метод разработки «сверху вниз» иначе называется методом последовательного уточнения алгоритма или методом пошаговой детализации.
Процесс последовательного уточнения алгоритма выглядит следующим образом.
На первом шаге мы считаем, что перед нами совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки задачи (рис. 1.1).
Рис. 1.1. Линейный алгоритм, являющийся результатом первого шага последовательного уточнения алгоритма
Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписаний (команд). Для этого:
- задачу разбивают на несколько частей, каждая из которых проще всей задачи;
- решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполнителя;
- при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний.
Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.
При использовании метода разработки «снизу вверх» спачала разрабатывается библиотека — множество отдельных небольших алгоритмов, которые могут понадобиться для решения некоторого класса задач. После этого разрабатывается основной алгоритм, содержащий обращения к алгоритмам из библиотеки.
Вы уже знакомы с исполнителем Робот. Он действует на клетчатом поле, между клетками которого могут быть стены.
Система команд исполнителя Робот:
В одном условии можно использовать несколько команд, применяя логические операции и, или, не.
Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл-ПОКА:
влево
нц пока сверху стена и снизу стена
закрасить
влево
кц
Под управлением этого алгоритма Робот закрасит все клетки коридора, находящиеся левее от него, и окажется в клетке левее коридора:
2. Командой вправо вернем Робота в коридор. Вернём Робота в исходную клетку. Эта клетка — первая незакрашенная клетка, находящаяся правее Робота. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вправо.
вправо
нц пока клетка закрашена
вправо
кц
Под управлением этого алгоритма Робот окажется в исходной клетке:
3. Выполнив команду вправо, Робот пройдёт исходную клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.
вправо
нц пока сверху стена и снизу стена
закрасить
вправо
кц
4. Так как, выполнив предыдущий алгоритм, Робот оказался правее коридора, командой влево вернём его в коридор. Возвращение в исходную клетку обеспечивается алгоритмом:
влево
нц пока клетка закрашена
влево
кц
5. По команде закрасить Робот закрашивает исходную клетку. Полностью программа управления Роботом выглядит так:
использовать Робот
алг
нач
влево
нц пока сверху стена и снизу стена
закрасить
влево
кц
вправо
нц пока клетка закрашена
вправо
кц
вправо
нц пока сверху стена и снизу стена
закрасить
вправо
кц
влево
нц пока клетка закрашена
влево
кц
закрасить
кон
Во многих случаях при разработке алгоритмов решения сложных задач используют вспомогательные алгоритмы. Например, это удобно, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности действий. Такую последовательность действий оформляют отдельным алгоритмом, который вызывают в нужных местах основного алгоритма. Один и тот же вспомогательный алгоритм может использоваться в разных программах. Вспомогательные алгоритмы делают более понятной структуру основного алгоритма.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма для решения некоторой подзадачи основной задачи.
Пример 1
В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого будет нарисован узор:
Начальное положение Робота отмечено ромбом; конечное положение значения не имеет.
Можно написать одну длинную программу, выполнив которую Робот закрасит все клетки, образующие этот узор. Но можно поступить иначе, обратив внимание на то, что в узоре трижды повторяется изображение одной и той же фигуры:
Разработав вспомогательный алгоритм для изображения этой фигуры, его можно вызвать нужное количество раз для построения требуемого узора.
использовать Робот
алг узор
нач
фигура
вправо; вниз
фигура
вправо; вверх
фигура
кон
алг фигура
нач
закрасить; вниз
закрасить; вправо; закрасить; вправо
закрасить; вверх; закрасить
кон
Выполните приведённый выше алгоритм в среде КуМир. Модифицируйте алгоритм таким образом, чтобы с его помощью можно было бы продолжить узор, дополнив его по горизонтали несколькими повторяющимися фигурами. Убедитесь в работоспособности разработанного алгоритма.
Каждый вспомогательный алгоритм получает уникальное имя, после которого указываются параметры алгоритма (при наличии) — имена переменных, обозначающих исходные данные (аргументы) и результаты вспомогательного алгоритма.
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 1.2), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — аргументы и результаты.
Рис. 1.2. Блок «предопределённый процесс»
Имя рассмотренного выше вспомогательного алгоритма — фигура; это вспомогательный алгоритм без параметров.