Основы алгоритмизации

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

Последовательное построение алгоритма

Существуют различные методы конструирования (разработки, по­строения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он на­зывается методом разработки «сверху вниз», нисходящим методом или методом пошаговой детализации.

Процесс последовательного построения алгоритма выглядит сле­дующим образом.

На первом шаге мы считаем, что перед нами совершенный испол­нитель, который «всё знает и всё умеет». Поэтому достаточно опреде­лить исходные данные и результаты алгоритма, а сам алгоритм пред­ставить в виде единого предписания — постановки задачи (рис. 3.13).

Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписании (команд). Для этого:

  • задачу разбивают на несколько частей, каждая из которых проще всей задачи;
  • решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполни­теля;

1.png

Рис.3.13 Линейный алгоритм, являющийся результатом первого этапа детализации задачи

  • при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представля­ются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.

Объединяя полученные предписания в единую совокупность вы­полняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.

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

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

1_1.png

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

1_2.png

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

4.png

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

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

2.png

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

2_4.png

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

2_2.png

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

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

2_5.png

2_6.png

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

2_7.png

2.png

5. По команде закрасить Робот закрашивает исходную точку.

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

алг

нач

      влево

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

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

кц

       вправо

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

      вправо

кц

      вправо

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

      закрасить; вправо

кц

      влево

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

      влево

кц

      закрасить

кон