Главная arrow Учебники arrow Информатика 9 класс Босова Л.Л. 2013 arrow §2.3 Конструирование алгоритмов

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

Конструирование алгоритмов, Последовательное построение алгоритма, Вспомогательный алгоритм, Формальные параметры, Фактические параметры, Рекурсивный алгоритм, Последовательное построение алгоритма, Разработка алгоритма методом последовательного уточнения для исполнителя Робот, Информатика 9 класс Босова, Информатика 9 класс

2.3.1. Последовательное построение алгоритма
Существуют различные методы конструирования (разработки, построения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он называется методом разработки «сверху вниз», нисходящим методом или методом пошаговой детализации.
Процесс последовательного построения алгоритма выглядит следующим образом.
На первом шаге мы считаем, что перед нами совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки задачи (рис. 2.2).
Линейный <a href='/slovar-spravochnik-po-terminam/programmnoe-obespechenie-avtomatizirovannyih-sistem/algoritm-algorithm.html
' target='_self'>алгоритм</a>, являющийся результатом первого этапа детализации задачи
Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписании (команд). Для этого:
 - задачу разбивают на несколько частей, каждая из которых проще всей задачи;
 - решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполнителя;
 - при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.

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

Команда

Описание команды

Вверх

Робот перемещается в соседнюю клетку в указанном направлении. Если в этом направлении между клетками стоит стена, то Робот разрушается

Вниз

Вправо

Влево

Закрасить

Робот закрашивает ту клетку, в которой находится

Сверху свободно

Проверка истинности условия отсутствия стены у соответствующей стороны той клетки, где находится Робот: стены нет - «истина», иначе «ложь»

Снизу свободно

Слева свободно

Справа свободно

Сверху стена

Проверка истинности условия наличия стены у соответствующей стороны той клетки, где находится Робот: стена есть - «истина», иначе «ложь»

Снизу стена

Слева стена

Справа стена

Клетка закрашена

Проверка истинности условия: клетка закрашена - «истина», иначе «ложь»

Если <условие> то

Последовательность команд

Все

Организация ветвления: если <условие> верно, то выполняется Последовательность команд>

нц

   пока <условие>

<последовательность команд>

кц

Организация цикла: пока <условие> верно, выполняется

<последовательность команд>

В одном условии можно использовать несколько команд, применяя логические операций И, ИЛИ, НЕ.
Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Алгоритм
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Алгоритм
Представим план действий Робота следующими укрупнёнными шагами (модулями):
План действий Робота
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл-ПОКА:

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


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

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


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

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

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

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

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

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


2.3.3. Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполйение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритмалгоритм, целиком используемый в составе другого алгоритма.
Пример 1. В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:
Алгоритм для исполнителя Робот
Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.

использовать Робот
алг узор
нач
   фигура
   вправо; вниз
   фигура
   вправо; вниз
   фигура
кон
алг фигура
нач
   закрасить; вниз
   закрасить; вправо; закрасить; вправо; закрасить
   вверх; закрасить
кон


При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.3), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Блок «предопределённый процесс»
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Пример 2.
Вспомним алгоритм вычисления степени с натуральным показателем у = аn. Соответствующая блок-схема:
Алгоритм вычисления степени с натуральным показателем
Степень с целым показателем у = ах, где х — целое число, а 0 вычисляется так:
Степень с целым показателем
В приведённой записи дважды фигурирует вычисление степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем. Соответствующая блок-схема:
Алгоритм вычисления степени с натуральным показателем
Алгоритм, представленный на блок-схеме, является основным по отношению к вызываемому в нём вспомогательному алгоритму.
Параметрами используемого вспомогательного алгоритма являются величины а, n, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.4):
1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного алгоритма.
Схема выполнения команды вызова вспомогательного алгоритма
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
Рассмотрим несколько примеров рекурсивных алгоритмов.
Пример 3. Алгоритм вычисления степени с натуральным показателем п для любого вещественного числа а можно представить в виде рекурсивного:
Алгоритм вычисления степени с натуральным показателем n
n-я степень числа а есть не что иное, как произведение аn-1 * а; в свою очередь, аn-1 = аn-2 * а и т. д.
Пример 4. Рекурсивный алгоритм положен в основу эффективного решения головоломки «Ханойская башня».
Ханойская башня
Пример 5. Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
Снежинка Коха
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.