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