Урок 27

 

---

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

Ключевые слова:

• последовательное построение алгоритма
• вспомогательный алгоритм
• формальные параметры
• фактические параметры
• рекурсивный алгоритм

2.3.2. Разработка алгоритма методом последовательного уточнения для исполнителя Робот

Вы уже знакомы с исполнителем Робот. Он действует на клетчатом поле, между клетками которого могут быть стены. Система команд исполнителя Робот:

Глава 2. Алгоритмизация и программирование

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

Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.

Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.

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

Представим план действий Робота следующими укрупнёнными шагами (модулями):

ж коридора левее исходной

2. Возвращение в исходное положение к коридора правее исходной

4. Возвращение в исходное положение

5. Закраска исходной клетки

Детализируем каждый из пяти модулей.

1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл ПОКА:

влево

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

 снизу стена

Под управлением этого алгоритма Робот закрасит все клетки ко­ридора, находящиеся левее от него, и окажется на клетке рядом с левой границей коридора.

2. Командой вправо вернём Робота в коридор. Наша задача — вернуть Робота в исходную точку. Эта точка имеет единственный отличительный признак — она не закрашена. Поэтому пока занимаемая

Глава 2. Алгоритмизация и программирование

Роботом клетка оказывается закрашенной, будем перемещать его вправо.

вправо

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

хц

Под управлением этого алгоритма Робот окажется в исходной клетке.

3. Выполнив команду вправо, Робот пройдёт исходную клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.

вправо

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

4. Так как, выполнив предыдущий алгоритм, Робот оказался пра­вее коридора, командой влево вернём его в коридор. Возвращение в исходную точку обеспечивается алгоритмом:

влево

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

5. По команде закрасить Робот закрашивает исходную клетку. Полностью программа управления Роботом выглядит так:

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

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

закрасить; влево кц

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

вправо кц

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

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

---

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа?
2. Почему при решении сложной задачи затруднительно сразу конкретизировать все необходимые действия?
3. В чём заключается метод последовательного уточнения при построении алгоритма?
4. Какая связь между методом последовательного построения алгоритма и такими процессами, как написание сочинения или подготовка к многодневному туристическому походу?

   ---

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

Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.

Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.

---