АЛГОРИТМ. Урок 2. Исполнитель алгоритма. | Учи Урок информатики

• Уроки Информатики
• Информатика в старших классах
• Основы программирования
• Алгоритмы

Основано на учебнике Босовой Людмилы Леонидовны

Каждый алгоритм предназначен для определённого исполнителя.

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

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

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

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

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

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

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

Рассмотрим примеры исполнителей.

Пример 5. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. Система команд Черепашки состоит из двух команд:

Вперёд n (где n — целое число) — вызывает передви­жение Черепашки на n шагов в направлении движения — в том направлении, куда развёрнуты её голова и корпус;

Направо m (где m — целое число) — вызывает измене­ние направления движения Черепашки на m градусов по часовой стрелке.

Запись Повтори к [<Команда1> <Команда2> … <Командаn>] означает, что последовательность команд в скобках повторится к раз.

Подумайте, какая фигура появится на экране после выполнения Чере­пашкой следующего алгоритма.

Повтори 12 [Направо 45 Вперёд 20 Направо 45]

Пример 6. Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:

1. — вычти 1
2. — умножь на 3

Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь но­мера команд. Например, алгоритм 21212 означает следующую после­довательность команд:

• умножь на 3
• вычти 1
• умножь на 3
• вычти 1
• умножь на 3

С помощью этого алгоритма число 1 будет преобразовано в 15: ((1*3-1)*3-1)*3 = 15.

При разработке алгоритма:

1. выделяются фигурирующие в задаче объекты, устанавливаются свойства объектов, отношения между объектами и возможные действия с объектами;
2. определяются исходные данные и требуемый результат;
3. определяется последовательность действий исполнителя, обес­печивающая переход от исходных данных к результату;
4. последовательность действий записывается с помощью команд, входящих в систему команд исполнителя.

Можно сказать, что алгоритм — модель деятельности исполните­ля алгоритмов.

Тэги:
алгоритм

Все статьи раздела

АЛГОРИТМ. Урок 2. Исполнитель алгоритма.АЛГОРИТМ. Урок 1. Понятие Алгоритма.Развивающая игра LightbotАЛГОРИТМ. Урок 3. Величины, переменные, константы.АЛГОРИТМ. Урок 4. Конструкция следование

• Коменты VK
• Анонимные коменты, G+ или Facebook

Please enable JavaScript to view the comments powered by Disqus.comments powered by Disqus

Алгоритмы и исполнители — Информатика 😉

Команда

/ Шаблоны проектирования
/ Модели поведения

Также известен как: Действие, Транзакция

Intent

Команда — это поведенческий шаблон проектирования, который превращает запрос в автономный объект, содержащий всю информацию о запросе. Это преобразование позволяет передавать запросы в качестве аргументов метода, откладывать выполнение запроса или ставить его в очередь, а также поддерживать операции, которые нельзя отменить.

Проблема

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

Все кнопки приложения являются производными от одного класса.

Хотя все эти кнопки выглядят одинаково, все они должны выполнять разные функции. Куда бы вы поместили код для различных обработчиков кликов этих кнопок? Самое простое решение — создать множество подклассов для каждого места, где используется кнопка. Эти подклассы будут содержать код, который должен выполняться по нажатию кнопки.

Множество подклассов кнопок. Что может пойти не так?

Вскоре вы понимаете, что этот подход глубоко ошибочен. Во-первых, у вас есть огромное количество подклассов, и это было бы нормально, если бы вы не рисковали сломать код в этих подклассах каждый раз, когда вы модифицируете базовый класс Button . Проще говоря, ваш код GUI стал неловко зависеть от изменчивого кода бизнес-логики.

Несколько классов реализуют одну и ту же функциональность.

А вот и самое безобразное. Некоторые операции, такие как копирование/вставка текста, необходимо будет вызывать из нескольких мест. Например, пользователь может нажать маленькую кнопку «Копировать» на панели инструментов, скопировать что-то через контекстное меню или просто нажать 9.0018 Ctrl+C на клавиатуре.

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

Решение

Хороший дизайн программного обеспечения часто основан на принципе разделения задач , что обычно приводит к разбиению приложения на слои. Самый распространенный пример: слой для графического пользовательского интерфейса и еще один слой для бизнес-логики. Слой GUI отвечает за рендеринг красивой картинки на экране, захват любого ввода и отображение результатов действий пользователя и приложения. Однако, когда дело доходит до чего-то важного, например расчета траектории движения Луны или составления годового отчета, уровень графического интерфейса делегирует работу нижележащему уровню бизнес-логики.

В коде это может выглядеть так: объект GUI вызывает метод объекта бизнес-логики, передавая ему некоторые аргументы. Этот процесс обычно описывается как отправка одним объектом другому запроса .

Объекты GUI могут напрямую обращаться к объектам бизнес-логики.

Шаблон Command предполагает, что объекты GUI не должны отправлять эти запросы напрямую. Вместо этого вы должны извлечь все детали запроса, такие как вызываемый объект, имя метода и список аргументов, в отдельный класс команды с одним методом, который запускает этот запрос.

Командные объекты служат связующим звеном между различными объектами графического интерфейса и бизнес-логики. Отныне объекту GUI не нужно знать, какой объект бизнес-логики получит запрос и как он будет обработан. Объект GUI просто запускает команду, которая обрабатывает все детали.

Доступ к уровню бизнес-логики с помощью команды.

Следующим шагом является реализация команд с одинаковым интерфейсом. Обычно он имеет только один метод выполнения, который не принимает параметров. Этот интерфейс позволяет использовать различные команды с одним и тем же отправителем запроса, не связывая его с конкретными классами команд. В качестве бонуса теперь вы можете переключать объекты команд, связанные с отправителем, эффективно изменяя поведение отправителя во время выполнения.

Возможно, вы заметили недостающую часть головоломки — параметры запроса. Объект GUI мог предоставить объекту бизнес-уровня некоторые параметры. Поскольку метод выполнения команды не имеет никаких параметров, как мы можем передать детали запроса получателю? Оказывается, команда должна быть либо предварительно сконфигурирована с этими данными, либо способна получить их самостоятельно.

Объекты графического интерфейса делегируют работу командам.

Вернемся к нашему текстовому редактору. После применения паттерна Command нам больше не нужны все эти подклассы кнопок для реализации различных действий при нажатии. Достаточно поместить одно поле в основание Button Класс, который хранит ссылку на объект команды и заставляет кнопку выполнять эту команду по щелчку.

Вы создадите набор классов команд для каждой возможной операции и свяжете их с определенными кнопками в зависимости от предполагаемого поведения кнопок.

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

В результате команды становятся удобным промежуточным уровнем, уменьшающим связь между графическим интерфейсом и уровнями бизнес-логики. И это лишь малая часть преимуществ, которые может предложить шаблон Command!

Аналогия из реального мира

Оформление заказа в ресторане.

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

Бумажный заказ служит командой. Он остается в очереди до тех пор, пока шеф-повар не будет готов его подать. Заказ содержит всю необходимую информацию, необходимую для приготовления блюда. Это позволяет шеф-повару сразу приступить к приготовлению, а не бегать, уточняя детали заказа у вас напрямую.

Структура

1. Класс Sender (также известный как Invoker ) отвечает за инициирование запросов. Этот класс должен иметь поле для хранения ссылки на объект команды. Отправитель запускает эту команду вместо отправки запроса непосредственно получателю. Обратите внимание, что отправитель не несет ответственности за создание объекта команды. Обычно он получает предварительно созданную команду от клиента через конструктор.

2. Интерфейс Command обычно объявляет только один метод для выполнения команды.

3. Конкретные команды реализуют различные виды запросов. Конкретная команда не должна выполнять работу сама по себе, а должна передавать вызов одному из объектов бизнес-логики. Однако ради упрощения кода эти классы можно объединить.

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

4. Класс Receiver содержит некоторую бизнес-логику. В качестве приемника может выступать практически любой объект. Большинство команд обрабатывают только детали того, как запрос передается получателю, в то время как сам получатель выполняет фактическую работу.

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

Псевдокод

В этом примере шаблон Команда помогает отслеживать историю выполненных операций и позволяет при необходимости отменить операцию.

Невыполнимые операции в текстовом редакторе.

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

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

 // Базовый класс команд определяет общий интерфейс для всех
// конкретные команды.
команда абстрактного класса
    приложение защищенного поля: Приложение
    редактор защищенного поля: Редактор
    резервная копия защищенного поля: текст
    команда конструктора (приложение: приложение, редактор: редактор)
        это.приложение = приложение
        this.editor = редактор
    // Сделать резервную копию состояния редактора.
    метод saveBackup()
        резервная копия = редактор.текст
    // Восстановить состояние редактора. 
    метод отмены() есть
        редактор.текст = резервная копия
    // Метод выполнения объявляется абстрактным, чтобы заставить все
    // конкретные команды для предоставления собственных реализаций.
    // Метод должен возвращать true или false в зависимости от того,
    // команда изменяет состояние редактора.
    абстрактный метод выполнить()
// Здесь идут конкретные команды.
класс CopyCommand расширяет команду
    // Команда копирования не сохраняется в истории, т.к.
    // не изменяет состояние редактора.
    метод выполнить ()
        app.clipboard = редактор.getSelection()
        вернуть ложь
класс CutCommand расширяет команду
    // Команда cut изменяет состояние редактора, поэтому
    // его нужно сохранить в историю. И он будет сохранен как
    // пока метод возвращает true.
    метод выполнить ()
        сохранить резервную копию ()
        app.clipboard = редактор.getSelection()
        редактор.deleteSelection()
        вернуть истину
класс PasteCommand расширяет команду
    метод выполнить ()
        сохранить резервную копию ()
        editor. replaceSelection(app.clipboard)
        вернуть истину
// Операция отмены также является командой.
класс UndoCommand расширяет команду
    метод выполнить ()
        приложение.отменить()
        вернуть ложь
// Глобальная история команд — это просто стек.
класс CommandHistory
    история частных полей: массив команд
    // Последний в...
    метод push(c: Command)
        // Поместите команду в конец массива истории.
    // ...первым вышел
    метод pop(): команда
        // Получить самую последнюю команду из истории.
// Класс редактора имеет фактические операции редактирования текста. Играет
// роль получателя: все команды заканчиваются делегированием
// выполнение методов редактора.
Редактор классов
    текст поля: строка
    метод getSelection() есть
        // Вернуть выделенный текст.
    метод deleteSelection() есть
        // Удалить выделенный текст.
    метод replaceSelection (текст) есть
        // Вставляем содержимое буфера обмена в текущую
        // позиция.
// Класс приложения устанавливает объектные отношения.  Он действует как
// отправитель: когда что-то нужно сделать, он создает команду
// объект и выполняет его.
приложение класса
    поле буфера обмена: строка
    field editors: массив редакторов
    поле activeEditor: Редактор
    история поля: CommandHistory
    // Код, который назначает команды объектам пользовательского интерфейса, может выглядеть
    // так.
    метод createUI() есть
        // ...
        копировать = функция() {выполнитькоманду(
            новая команда копирования (это, активный редактор)) }
        copyButton.setCommand(копировать)
        ярлыки.onKeyPress("Ctrl+C", копировать)
        вырезать = функция () { выполнить команду (
            новая CutCommand (это, активный редактор)) }
        cutButton.setCommand(вырезать)
        ярлыки.onKeyPress("Ctrl+X", вырезать)
        вставить = функция() {выполнитькоманду(
            новая команда PasteCommand (это, активный редактор)) }
        pasteButton.setCommand(вставить)
        ярлыки.onKeyPress("Ctrl+V", вставить)
        отменить = функция () { выполнить команду (
            новая UndoCommand (это, активный редактор)) }
        undoButton. setCommand(отменить)
        ярлыки.onKeyPress("Ctrl+Z", отменить)
    // Выполняем команду и проверяем, нужно ли ее добавить в
    // история.
    метод executeCommand (команда)
        если (команда.выполнить)
            history.push(команда)
    // Возьмем самую последнюю команду из истории и запустим ее
    // метод отмены. Обратите внимание, что мы не знаем класс этого
    // команда. Но нам и не надо, так как командование знает
    // как отменить свое действие.
    метод отмены() есть
        команда = история.поп()
        если (команда != ноль)
            команда.отменить()
 

Применимость

Используйте шаблон Command, если вы хотите параметризовать объекты с помощью операций.

Шаблон Command может превратить вызов определенного метода в автономный объект. Это изменение открывает много интересных применений: вы можете передавать команды в качестве аргументов метода, хранить их внутри других объектов, переключать связанные команды во время выполнения и т.  д.

Вот пример: вы разрабатываете компонент графического интерфейса, например контекстное меню. , и вы хотите, чтобы ваши пользователи могли настраивать элементы меню, которые запускают операции, когда конечный пользователь щелкает элемент.

Используйте шаблон Command, если вы хотите поставить операции в очередь, запланировать их выполнение или выполнить их удаленно.

Как и любой другой объект, команду можно сериализовать, что означает преобразование ее в строку, которую можно легко записать в файл или базу данных. Позже строка может быть восстановлена ​​как исходный объект команды. Таким образом, вы можете откладывать и планировать выполнение команды. Но это еще не все! Точно так же вы можете ставить в очередь, регистрировать или отправлять команды по сети.

Используйте шаблон Command, если вы хотите реализовать обратимые операции.

Хотя существует множество способов реализации отмены/возврата, шаблон Command, пожалуй, самый популярный из всех.

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

Этот метод имеет два недостатка. Во-первых, не так просто сохранить состояние приложения, потому что некоторые из них могут быть приватными. Эту проблему можно решить с помощью шаблона Memento.

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

Как реализовать

1. Объявите командный интерфейс с единым методом выполнения.

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

3. Определите классы, которые будут действовать как отправители . Добавьте в эти классы поля для хранения команд. Отправители должны общаться со своими командами только через командный интерфейс. Отправители обычно не создают объекты команд самостоятельно, а получают их из клиентского кода.

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

5. Клиент должен инициализировать объекты в следующем порядке:

   • Создание приемников.
   • Создайте команды и при необходимости свяжите их с приемниками.
   • Создайте отправителей и свяжите их с определенными командами.

Плюсы и минусы

• Принцип единой ответственности . Вы можете отделить классы, которые вызывают операции от классов, которые выполняют эти операции.
• Открытый/Закрытый принцип . Вы можете вводить в приложение новые команды, не нарушая существующий клиентский код.
• Вы можете реализовать отмену/возврат.
• Можно реализовать отложенное выполнение операций.
• Вы можете собрать набор простых команд в сложный.

• Код может стать более сложным, так как вы вводите совершенно новый слой между отправителями и получателями.

Связь с другими шаблонами

• Chain of Responsibility, Command, Mediator и Observer обращаются к различным способам соединения отправителей и получателей запросов:

  • Цепочка ответственности передает запрос последовательно по динамической цепочке потенциальных получателей, пока один из них не обработает его.
  • Команда устанавливает однонаправленные соединения между отправителями и получателями.
  • Посредник устраняет прямые соединения между отправителями и получателями, заставляя их взаимодействовать косвенно через объект-посредник.
  • Observer позволяет получателям динамически подписываться и отменять подписку на получение запросов.

• Обработчики в цепочке ответственности могут быть реализованы как команды. В этом случае вы можете выполнять множество различных операций над одним и тем же объектом контекста, представленным запросом.

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

• Вы можете использовать Command и Memento вместе при реализации «отмены». В этом случае команды отвечают за выполнение различных операций над целевым объектом, а сувениры сохраняют состояние этого объекта непосредственно перед выполнением команды.

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

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

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

• Prototype может помочь, когда вам нужно сохранить копии команд в истории.

• Посетитель можно рассматривать как мощную версию шаблона Command. Его объекты могут выполнять операции над различными объектами разных классов.

Примеры кода

Документация JDK 20 — Главная