§16. Использование основных алгоритмических конструкций для исполнителя Робот

Последовательное выполнение команд в программе определяется структурой следование. Для организации повторяющихся действий в алгоритме используется команда цикла. Команда ветвления позволяет выполнять одну или другую последовательность команд в зависимости от истинности условия.

Следование, цикл и ветвление – базовые алгоритмические конструкции. Используя эти конструкции как элементы некоего «конструктора», можно составлять и разрабатывать любые алгоритмы.

Команды цикла и ветвления управляют порядком выполнения других команд в программе и относятся к командам управления. Использование алгоритмической конструкции следование предполагает отсутствие управляющих конструкций. Рассмотрим примеры алгоритмов, содержащих несколько алгоритмических конструкций.

Пример 16.1. Написать программу для закраски некоторых клеток на поле. Окончание движения Робота определяет стена справа. По пути нужно закрасить те клетки, сверху над которыми есть стена.

Для решения задачи Робот при движении вправо должен проверять каждую клетку на своем пути. Если условие сверху стена выполняется, то Робот закрашивает эту клетку. После проверки клетки Робот сдвигается вправо. Эти действия выполняются в цикле пока справа нет стены.
После цикла необходима команда ветвления, так как для крайней клетки поля условие нет стены справа является ложным и клетка в цикле не закрашивается.

В этой задаче внутри конструкции цикла используется конструкция ветвления.

Пример 16.2. Робот должен дойти до конца «коридора» переменного размера. В «коридоре» может быть поворот влево или вправо.

Для решения задачи Робот сначала перемещается вверх, до тех пор, пока истинно условие нет стены сверху. Стена, появившаяся сверху, означает, что начался поворот «коридора». Если слева нет стены, то в «коридоре» надо поворачивать влево, иначе «коридоре» Робот поворачивает вправо.

Дальше двигаемся в выбранном направлении, пока не дойдем до стены.
При решении данной задачи используются сначала конструкцию цикла, а затем конструкцию ветвления. Каждая последовательность команд в команде ветвления в свою очередь является циклом.

Пример 16.3. *Роботу необходимо переместиться из верхнего левого угла поля в нижний левый угол.

При этом, на поле присутствуют стены. Робот начинает движение вправо до правой границы поля и спускается на одну клетку вниз. Затем, движение продолжается влево до левой границы поля и, также, – спуск вниз на одну клетку. Эти действия Робот должен повторить 4 раза.

В данной задаче внутри цикла с параметром используются два других цикла с предусловием.

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

Один из возможных вариантов вложенных циклов представлена на блок-схеме в примере 16.4. Как видно из примеров, базовые алгоритмические структуры можно комбинировать друг с другом так, как этого требует алгоритм решения задачи.

Перед человеком постоянно возникают разнообразные задачи, для которых находят различные алгоритмы решения. При всем многообразии алгоритмов для их записи достаточно трех алгоритмических конструкций (структур): следование, цикл, ветвление.
Это положение было выдвинуто в середине 70-х годов прошлого века нидерландским ученым Эдсгером Вибе Дейкстрой (1930 – 2002). Его труды оказали влияние на развитие информатики и информационных технологий. Э.Дейкстра является одним из разработчиков концепции структурного программирования, участвовал в разработке языка программирования Алгол. Известен своими разработками в области математической логики и теории графов.

Пример 16.1. Одна из возможных начальных обстановок.

Программа для исполнителя Робот:

from pyrob.api import *

@task
def prim_16_1():
      while not wall_right():
            if wall_down():
                 fill_cell()
           move_right()
      if wall_up():
            fill_cell()

run_tasks()

Пример 16.2. Одна из возможных начальных обстановок.

Другая обстановка:

Программа для исполнителя Робот:

from pyrob.api import *

@task
def prim_16_2():
      while not wall_up():
             move_up()
      if wall_left():
         while not wall_right():
                  move_right()
      else:
         while not wall_left():
                 move_left():

run_tasks()

Пример 16.3. *Начальная обстановка

Программа для исполнителя Робот:

from pyrob.api import *

@task
def prim_16_3():
      for i in range (4):
            while wall_down():
                   move_right()
            move_down()
            while wall_down():
                 move_left()
            move_down()

run_tasks()

Пример 16.4. Блок-схема вложенных циклов.

1. Назовите базовые алгоритмические конструкции.
2. Какие базовые алгоритмические конструкции относят к элементам управления?
3. Приведите примеры использования базовых алгоритмических конструкций.
4. *Что такое вложенный цикл?

Упражнения

1. Объясните, какие алгоритмические конструкции используются в приведенных ниже программах. Нарисуйте блок-схемы данных алгоритмов. Предложите пример начальной обстановки, в которой алгоритм выполнится корректно.

а)	б)
from pyrob.api import *@task def upr_16_1(): while wall_left(): fill_cell() move_down()run_tasks()	from pyrob.api import *@task def upr_16_2(): while cell_is_filled(): if not all_left(): move_left()run_tasks()

2. Для решения задачи upr_16_2 Миша написал программу, но она работает неправильно. Какие ошибки допустил Миша?

from pyrob.api import *

@task
def upr_16_2():
    while wall_right():
            if wall_up() or wall_down():
                 fill_cell()
            move_right()
            if wall_up() and wall_down():
                 fill_cell()