Урок 27
Алгоритм — модель деятельности исполнителя алгоритмов
Исполнитель Чертежник. Управление Чертежником
Работа в среде «Алгоритмика»

Алгоритм — модель деятельности исполнителя алгоритмов

Рассмотрим более подробно класс объектов, называемых исполнителями.

Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определенный набор команд. Команды, которые может выполнить конкретный исполнитель, образуют систему команд исполнителя (СКИ).

Класс исполнителей необычайно разнообразен. Прежде всего, в нем выделяют два типа исполнителей: формальных и неформальных. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.

Например, при многократном прослушивании кассеты с любимой мелодией вы можете быть уверены, что она воспроизводится проигрывателем (формальным исполнителем) одинаково. Но вряд ли кому-нибудь из певцов (неформальному исполнителю) удастся несколько раз совершенно одинаково исполнить песню из своего репертуара.

Как правило, человек выступает в роли неформального исполнителя. Формальными исполнителями являются преимущественно технические устройства. Человек в роли неформального исполнителя сам отвечает за свои действия. За действия формального исполнителя отвечает управляющий им объект.

Рассмотрим более подробно множество формальных исполнителей. Формальные исполнители необычайно разнообразны, но для каждого из них можно указать круг решаемых задач, среду, систему команд, систему отказов и режимы работы.

1. Круг решаемых задач. Каждый исполнитель создается для решения определенного класса задач.

2. Среда исполнителя. Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя.

3. Система команд исполнителя. Предписание о выполнении отдельного законченного действия исполнителя называется командой. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует СКИ - систему команд исполнителя.

4. Система отказов исполнителя. Отказ «не понимаю» возникает тогда, когда исполнителю подается команда, не входящая в его СКИ. Отказ «не могу» возникает тогда, когда команда из СКИ не может быть им выполнена в конкретных условиях среды.

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

Управление — это процесс целенаправленного воздействия одних объектов на другие.

Исполнители являются объектами управления. Управлять ими можно, составив для них алгоритм.

Алгоритм — это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи. Можно сказать, что алгоритм — модель деятельности исполнителя алгоритмов.

Алгоритмы могут быть записаны в виде таблицы, нумерованного списка на естественном языке или изображены с помощью блок-схемы. Программа — это алгоритм, записанный по правилам понятного исполнителю-компьютеру языка.

Алгоритм разрабатывается для решения некоторой задачи или класса задач. При этом:

1) выделяются фигурирующие в задаче объекты, устанавливаются свойства объектов, отношения между объектами и возможные действия с объектами;

2) определяются исходные данные и результат;

3) определяется точная последовательность действий исполнителя, обеспечивающая переход от исходных данных к результату;

4) последовательность действий записывается на языке, понятном исполнителю.

Коротко о главном

Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определенный набор команд. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному. Для каждого формального исполнителя можно указать круг решаемых задач, среду, систему команд, систему отказов и режимы работы.

Управление — это процесс целенаправленного воздействия одних объектов на другие. Исполнители являются объектами управления. Управлять ими можно, составив для них алгоритм.

Алгоритм — это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи. Можно сказать, что алгоритм — модель деятельности исполнителя алгоритмов.

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

1. Определите типы исполнителей в предложенных ситуациях. Будьте готовы обосновать свой ответ.

а) Симфонический оркестр исполняет музыкальное произведение.
б) Ученик 7 класса решает домашнее задание по алгебре.
в) Ученик 7 класса списывает домашнее задание у своей одноклассницы.
г) Фармацевт готовит лекарство по рецепту.
д) Врач устанавливает причину плохого самочувствия пациента.
е) Автомат на конвейере наполняет бутылки лимонадом.
ж) Компьютер выполняет программу проверки правописания.

2. Горничная каждое утро, убирая свой этаж, пылесосит ковровую дорожку.

Назовите исполнителей в этой задаче. Укажите их типы.

3. Приведите 2-3 примера формальных исполнителей. Приведите пример, когда человек выступает в роли формального исполнителя.

4. Приведите примеры исполнителей, встречающихся в русских народных сказках. Определите их типы.

5. На вход «черного ящика» подается число 125. О чем в этом случае говорит отказ:
а) «не могу»;
б) «не понимаю»?

6. Рассмотрите приложение Калькулятор в качестве формального исполнителя.

Исполнитель Чертежник. Управление Чертежником.
Работа в среде «Алгоритмика»

Управление исполнителем Чертежник

Знакомимся с Чертежником

Исполнитель Чертежник предназначен для построения рисунков на координатной плоскости.

При задании точек этой координатной плоскости, в отличие от того, как это принято в математике, координаты х и у разделяются запятой. Например, координаты выделенной на рис. 3.1 точки будут записаны так: (1, 1).

Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след — отрезок от предыдущего положения пера до нового. При перемещении поднятого пера никакого следа на плоскости не остается. В начальном положении перо Чертежника всегда поднято и находится в точке (0, 0).

По команде подними перо Чертежник поднимает перо. Если перо уже было поднято, Чертежник игнорирует эту команду: он не меняет положение пера и не сообщает об отказе. Иначе говоря, каким бы ни было положение пера до команды подними перо, после этой команды оно будет поднятым.

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

Рисунки Чертежник выполняет с помощью команд переведи в точку и сдвинь на вектор.

По команде переведи в точку (а, b) Чертежник сдвигается в точку с координатами (а, b). На рис. 3.2 показаны результаты выполнения команды переведи в точку (2, 3) при различных положениях пера до этой команды. Видно, что независимо от предыдущего положения перо оказывается в точке (2, 3), но длина и направление отрезка, который при этом чертится, могут быть различны. Команду переведи в точку называют командой абсолютного смещения.

♦ Назовите координаты точек, в которых находился Чертежник до выполнения команды переведи в точку (2, 3).

♦ В каком случае в результате выполнения команды переведи в точку (2, 3) из различных показанных на рис. 3.2 начальных положений не будет прочерчен ни один отрезок?

Пусть перо Чертежника находится в точке (х, у). По команде сдвинь на вектор (а, b) Чертежник отсчитывает а единиц вправо вдоль горизонтальной оси (оси абсцисс), b единиц вверх вдоль вертикальной оси (оси ординат) и сдвигает перо в точку с координатами (х + а; у + b). Таким образом, координаты, указанные в команде, отсчитываются не от начала координат, а относительно текущего положения пера Чертежника. Поэтому команду сдвинь на вектор называют командой относительного смещения.

На рис. 3.3 показаны результаты выполнения команды сдвинь на вектор (2, 3) при различных положениях пера до этой команды. Из рисунка видно, что положение пера после этой команды зависит от его предыдущего положения, зато в результате получаются отрезки, длина и направление которых одинаковы. В математике направленные отрезки называются векторами, отсюда и происходит название команды.

♦ Назовите координаты точек, в которых находилось перо Чертежника до выполнения команды сдвинь на вектор (2, 3) и куда оно переместилось после выполнения этой команды.

♦ Как будет выполняться команда сдвинь на вектор (а, Ь),если:
а) а < 0;
б) Ъ < 0;
в) а < 0 и b < 0?

Чертежник может исполнять только правильно записанные команды. Например, если вместо команды сдвинь на вектор написать здвинь на вектор, то Чертежник эту запись не поймет и сразу же сообщит об ошибке. Ошибки в записи команд называются синтаксическими.

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

Пример алгоритма управления Чертежником

Изобразим с помощью Чертежника треугольник, положение вершин которого на координатной плоскости определяется парами чисел (1, 1), (3, 5), (5, 2) (рис. 3.4).

Так как в начале работы перо Чертежника всегда поднято, то для рисования треугольника с заданными координатами достаточно выполнить следующую последовательность команд:

переведи в точку (1, 1)
опусти перо
переведи в точку (3, 5)
переведи в точку (5, 2)
переведи в точку (1, 1)

Предложите другие варианты выполнения этого задания. При этом число команд не должно превышать пяти (есть пять других вариантов).

А теперь составим такой алгоритм управления Чертежником, чтобы с его помощью в произвольном месте координатной плоскости можно было нарисовать прямоугольник со сторонами, параллельными координатным осям, длины которых равны 2 и 4 единицам.

Зафиксируем одну из вершин прямоугольника в точке (1, 1). Нужный рисунок на координатной плоскости может выглядеть, как показано на рис. 3.5.

♦ Предложите другой вариант рисунка, удовлетворяющий заданным условиям: одна из вершин прямоугольника расположена в точке (1, 1), а длины его сторон равны 2 и 4 единицам? (Существует еще семь вариантов.)

Можно определить координаты каждой из вершин этого прямоугольника и для его изображения составить следующую программу:

переведи в точку (1, 1)
опусти перо
переведи в точку (1, 3)
переведи в точку (5, 3)
переведи в точку (5, 1)
переведи в точку (1, 1)

Этот алгоритм не будет решать поставленную задачу, если изменить координаты начальной точки (рис. 3.6). Изменение координат одной из вершин повлечет за собой пересчет координат всех вершин прямоугольника. Причем это придется делать самому разработчику алгоритма.

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

Пусть (х, у) — координаты вершины А прямоугольника ABCD (рис. 3.7).

Тогда координаты вершины В можно записать как (х, у + 2), вершины С — как (х + 4, у 4- 2), вершины D — как (х + 4, у) (рис. 3.8).

Чтобы изобразить отрезок АВ, воспользуемся командой сдвинь на вектор (0, 2).

В результате Чертежник сдвинет перо из точки с координатами (х, у) в точку с координатами (х + 0, у + 2).

По команде сдвинь на вектор (4, 0) перо окажется в точке (х + 4, у + 2). Чтобы из этой точки перейти в точку (х + 4, у + 0), следует выполнить команду сдвинь на вектор (0, -2). По команде сдвинь на вектор (-4, 0) перо Чертежника прочертит отрезок к точке А:

Если в качестве вершины А зафиксировать точку с ко-ординатами (1, 1), то программа будет выглядеть так:

переведи в точку(1, 1)
опусти перо
сдвинь на вектор (0, 2)
сдвинь на вектор (4, 0)
сдвинь на вектор (0, -2)
сдвинь на вектор (-4, 0)

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

переведи в точку (5, 5)

С помощью команды абсолютного смещения рисунок «привязывается» к строго определенным точкам координатной плоскости. Она используется чаще всего для установки начального положения пера Чертежника.

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