Представление алгоритмов в виде блок-схем
Блок-схемой будем называть такое графическое представление алгоритма, когда отдельные действия (или команды) представляются в виде геометрических фигур – блоков. Внутри блоков указывается информация о действиях, подлежащих выполнению. Связь между блоками изображают с помощью линий, называемых линиями связи, обозначающих передачу управления.
Существует Государственный стандарт, определяющий правила создания блок-схем. Конфигурация блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19.701-90 «Схемы алгоритмов и программ». В табл. 2.1 приведены обозначения некоторых элементов, которых будет вполне достаточно для изображения алгоритмов при выполнении студенческих работ.
Правила составления блок-схем:
Каждая блок-схема должна иметь блок «Начало» и один блок «Конец».
«Начало» должно быть соединено с блоком «Конец» линиями потока по каждой из имеющихся на блок-схеме ветвей.
В блок-схеме не должно быть блоков, кроме блока «Конец», из которых не выходит линия потока, равно как и блоков, из которых управление передается «в никуда».
Блоки должны быть пронумерованы. Нумерация блоков осуществляется сверху вниз и слева направо, номер блока ставится вверху слева, в разрыве его начертания.
Блоки связываются между собой линиями потока, определяющими последовательность выполнения блоков. Линии потоков должны идти параллельно границам листа. Если линии идут справа налево или снизу вверх, то стрелки в конце линии обязательны, в противном случае их можно не ставить.
По отношению к блокам линии могут быть входящими и выходящими. Одна и та же линия потока является выходящей для одного блока и входящей для другого.
От блока «Начало» в отличие от всех остальных блоков линия потока только выходит, так как этот блок – первый в блок-схеме.
Блок «Конец» имеет только вход, так как это последний блок в блок-схеме.
Для простоты чтения желательно, чтобы линия потока входила в блок «Процесс» сверху, а выходила снизу.
Чтобы не загромождать блок-схему сложными пересекающимися линиями, линии потока можно разрывать. При этом в месте разрыва ставятся соединители, внутри которых указываются номера соединяемых блоков. В блок-схеме не должно быть разрывов, не помеченных соединителями.
Чтобы не загромождать блок, можно информацию о данных, об обозначениях переменных и т.п. размещать в комментариях к блоку.
Название блока
Обозначение блока
Назначение блока
Начало/Конец программы или подпрограммы
Обработка данных (вычислительное действие или последовательность вычислительных действий)
Ветвление, выбор, проверка условия. В блоке указывается условие или вопрос, который определяет дальнейшее направление выполнения алгоритма
Заголовок счетного цикла
Обращение к процедуре
Маркировка разрыва линии потока
Используется для размещения пояснений к действиям
Горизонтальные и вертикальные потоки
Линии связей между блоками, направление потоков
Тип алгоритма определяется характером решаемой в соответствии с его командами задачи. Различают три типа алгоритмов: линейные, разветвляющиеся, циклические.
Линейный алгоритм состоит из упорядоченной последовательности действий, не зависящей от значений исходных данных, при этом каждая команда выполняется только один раз строго после той команды, которая ей предшествует.
Таким, например, является алгоритм вычисления по простейшим безальтернативным формулам, не имеющий ограничений на значения входящих в эти формулы переменных. Как правило, линейные процессы являются составной частью более сложного алгоритма.
Разветвляющимися называются алгоритмы, в которых в зависимости от значения какого-то выражения или от выполнения некоторого логического условия дальнейшие действия могут производиться по одному из нескольких направлений.
Каждое из возможных направлений дальнейших действий называется ветвью.
В блок-схемах разветвление реализуется специальным блоком «Решение». Этот блок предусматривает возможность двух выходов. В самом блоке «Решение» записывается логическое условие, от выполнения которого зависят дальнейшие действия.
Различают несколько видов разветвляющихся алгоритмов.
1. «Обход» – такое разветвление, когда одна из ветвей не содержит ни одного оператора, т.е. как бы обходит несколько действий другой ветви.
2. «Разветвление» – такой тип разветвления, когда в каждой из ветвей содержится некоторый набор действий.
3. «Множественный выбор» – особый тип разветвления, когда каждая из нескольких ветвей содержит некоторый набор действий. Выбор направления зависит от значения некоторого выражения.
Циклические алгоритмы применяются в тех случаях, когда требуется реализовать многократно повторяющиеся однотипные вычисления. Цикл – это последовательность действий, которая может выполняться многократно, т.е. более одного раза.
циклы с известным числом повторений (или со счетчиком);
циклы с неизвестным числом повторений (циклы с предусловием и циклы с постусловием).
В любом цикле должна быть переменная, которая управляет выходом из цикла, т.е. определяет число повторений цикла.
Последовательность действий, которая должна выполняться на каждом шаге цикла (т.е. при каждом повторении цикла), называется телом цикла или рабочей частью цикла.
Блок-схемы алгоритмов. ГОСТ. Примеры
Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.
Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.
Содержание:
Элементы блок-схем алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.
Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов, но в текущей статье они, как и ряд специфических символов, не рассматриваются. Рассмотрены лишь основные символы, которых всегда достаточно студентам.
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
На каждом шаге алгоритма выбирается первый элемент необработанной части массива и вставляется в отсортированную так, чтобы в ней сохранялся требуемый порядок следования элементов. Вставка может выполняться как в конец массива, так и в середину. При вставке в середину необходимо сдвинуть все элементы, расположенные «правее» позиции вставки на один элемент вправо. В алгоритме используется два цикла — в первом выбираются элементы необработанной части, а во втором осуществляется вставка.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны — алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того.
На блок-схеме показано каким образом может использоваться символ перехода — его можно использовать не только для соединения частей схем, размещенных на разных листах, но и для сокращения количества линий. В ряде случаев это позволяет избежать пересечения линий и упрощает восприятие алгоритма.
Сортировка пузырьком
Сортировка пузырьком, как и сортировка вставками, использует два цикла. Во вложенном цикле выполняется попарное сравнение элементов и, в случае нарушения порядка их следования, перестановка. В результате выполнения одной итерации внутреннего цикла, максимальный элемент гарантированно будет смещен в конец массива. Внешний цикл выполняется до тех пор, пока весь массив не будет отсортирован.
Блок-схема алгоритма сортировки пузырьком
На блок-схеме показано использование символов начала и конца цикла. Условие внешнего цикла (А) проверяется в конце (с постусловием), он работает до тех пор, пока переменная hasSwapped имеет значение true. Внутренний цикл использует предусловие для перебора пар сравниваемых элементов. В случае, если элементы расположены в неправильном порядке, выполняется их перестановка посредством вызова внешней процедуры (swap). Для того, чтобы было понятно назначение внешней процедуры и порядок следования ее аргументов, необходимо писать комментарии. В случае, если функция возвращает значение, комментарий может быть написан к символу терминатору конца.
Сортировка выбором
В сортировке выбором массив разделяется на отсортированную и необработанную части. Изначально отсортированная часть пустая, но постепенно она увеличивается. Алгоритм производит поиск минимального элемента необработанной части и меняет его местами с первым элементом той же части, после чего считается, что первый элемент обработан (отсортированная часть увеличивается).
Блок-схема сортировки выбором
На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива, поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort, … .
На блоге можно найти другие примеры блок-схем:
Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word, но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd [5], обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.
Нужны ли блок-схемы? Альтернативы
Частные конторы никакие блок-схемы не используют, в книжках по алгоритмам [6] вместо них применяют словесное описание (псевдокод) как более краткую форму. Возможно блок-схемы применяют на государственных предприятиях, которые должны оформлять документацию согласно требованиям ЕСПД, но есть сомнения — даже для регистрации программы в Государственном реестре программ для ЭВМ никаких блок-схем не требуется.
Тем не менее, рисовать блок-схемы заставляют школьников (примеры из учебников ГОСТ не соответствуют) — выносят вопросы на государственные экзамены (ГИА и ЕГЭ), студентов — перед защитой диплом сдается на нормоконтроль, где проверяется соответствие схем стандартам.
Разработка блок-схем выполняется на этапах проектирования и документирования, согласно каскадной модели разработки ПО, которая сейчас почти не применяется, т.к. сопровождается большими рисками, связанными с ошибками на этапах проектирования.
Появляются подозрения, что система образования прогнила и отстала лет на 20, однако аналогичная проблема наблюдается и за рубежом. Международный стандарт ISO 5807:1985 мало чем отличается от ГОСТ 19.701-90, более нового стандарта за рубежом нет. Там же производится множество программ для выполнения этих самых схем — Dia, MS Visio, yEd, …, а значит списывать их не собираются. Вместо блок-схем иногда применяют диаграммы деятельности UML [6], однако удобнее они оказываются, разве что при изображении параллельных алгоритмов.
Периодически поднимается вопрос о том, что ни блок-схемы, ни UML не нужны, да и документация тоже не нужна. Об этом твердят программисты, придерживающиеся методологии экстремального программирования (XP) [7], ходя даже в их кругу нет единого мнения.
В ряде случаев, программирование невозможно без рисования блок-схем, т.к. это один процесс — существуют визуальные языки программирования, такие как ДРАКОН [8], кроме того, блок-схемы используются для верификации алгоритмов (формального доказательства их корректности) методом индуктивных утверждений Флойда [9].
В общем, единого мнения нет. Очевидно, есть области, в которых без чего-то типа блок-схем обойтись нельзя, но более гибкой альтернативы нет. Для формальной верификации необходимо рисовать подробные блок-схемы, но для проектирования и документирования такие схемы не нужны — я считаю разумным утверждение экстремальных программистов о том, что нужно рисовать лишь те схемы, которые помогают в работе и не требуют больших усилий для поддержания в актуальном состоянии [10].
Полное руководство по блок-схеме
Блок-схема используется для отображения последовательных шагов в процессе. В таких диаграммах используется ряд взаимосвязанных символов для отображения всего процесса, что упрощает его понимание и помогает в общении с другими. Блок-схемы можно использовать для объяснения работы сложного и/или абстрактного процесса, системы, концепции или алгоритма. Блок-схемы также могут помочь в планировании и разработке процессов или улучшении существующих процессов.
Почему блок-схемы актуальны и сегодня?
Блок-схемы могут предоставить пошаговые иллюстрации для отображения сложных ситуаций, таких как программирование или бизнес-процессы. Существует множество типов диаграмм процессов, в том числе плавающие диаграммы, такие как межфункциональные диаграммы, диаграммы возможностей или диаграммы процессов развертывания.
Давайте рассмотрим еще несколько причин, по которым блок-схемы являются эффективным дополнением к процессу программирования.
Вот преимущества, которые могут принести блок-схемы.
- Легко учить.
- Мгновенная связь.
- Эффективный анализ
- Хорошо для нетехнических.
- Повышенная эффективность.
- Решение проблем.
- Визуальный алгоритм
- Правильная отладка
- Процедурное описание
Элементы блок-схемы?
Разные символы означают разные вещи, и каждый символ имеет свою особую форму. Метка каждого шага написана внутри формы символа; блок-схемы используют изогнутые прямоугольники, чтобы показать начало и конец процесса; сегменты линий или стрелки используются, чтобы показать направление или переход от одного шага к другому; простые инструкции или прямоугольники действий используются, чтобы указать, когда необходимо принять решение, и используются ромбовидные формы. В дополнение к ним есть много других символов, которые можно использовать в блок-схемах.
Блок-схемы могут быть горизонтальными или вертикальными.
Символы блок-схемы
Различные формы блок-схем имеют разные общепринятые значения. Значения некоторых из наиболее распространенных форм следующие:
Терминатор
Символ завершения представляет собой начальную или конечную точку системы.
Прямоугольник указывает на некоторую конкретную операцию.
Документ
Представляет собой распечатку, такую как документ или отчет.
Решение
Ромб представляет собой решение или точку ветвления. Линии, выходящие из ромба, указывают на разные возможные ситуации, ведущие к разным подпроцессам.
Данные
Он представляет информацию, входящую или выходящую из системы. Ввод может быть заказом от клиента. Результатом может быть продукт, который должен быть доставлен.
Ссылка на странице
Этот символ будет содержать букву внутри. Это указывает на то, что поток продолжается на совпадающем символе, содержащем ту же букву, в другом месте на той же странице.
Справочник вне страницы
Этот символ будет содержать букву внутри. Это указывает на то, что поток продолжается на совпадающем символе, содержащем ту же букву, где-то еще на другой странице.
Задержка или узкое место
Обозначает задержку или узкое место.
Поток
Линии представляют поток последовательности и направление процесса.
Использование блок-схем
- Документировать процесс
- Развивать понимание того, как осуществляется процесс
- Сообщите другим, как выполняется процесс
- При планировании проекта
- мозговой штурм идеи
- Отладка функции или программы
- Объясните процедуру
- Исследуйте процесс, который нуждается в улучшении
- Когда есть необходимость в улучшении коммуникации между людьми, вовлеченными в один и тот же процесс
Пример блок-схемы — простые алгоритмы
Блок-схему также можно использовать для визуализации алгоритмов, независимо от ее сложности. Вот пример, показывающий, как можно использовать блок-схему для демонстрации простого процесса суммирования.
Пример блок-схемы – расчет прибыли и убытков
В приведенном ниже примере блок-схемы показано, как можно рассчитать прибыль и убыток.
Используйте блок-схему с разными уровнями детализации
Блок-схема высокого уровня, показывающая от шести до двенадцати шагов, дает панорамное представление о процессе. Эти блок-схемы ясно показывают основные блоки деятельности или основные компоненты системы в процессе.
Блок-схемы высокого уровня особенно полезны на ранних этапах проекта. Подробная блок-схема представляет собой крупный план процесса, обычно показывающий десятки шагов. Эти блок-схемы упрощают выявление циклов доработки и сложности процесса.
Подробные блок -схемы полезны после того, как команды точно определили проблемы или когда они вносят изменения в процесс.
Блок-схема дорожки для плавания
Базовая блок-схема состоит из ряда шагов процесса, соединенных стрелками, показывающими порядок операций, который считается одномерным. Блок-схема дорожек (также известная как кросс-функциональная блок-схема) обеспечивает дополнительное измерение, назначая каждому шагу процесса категорию. Чаще всего категорией является стейкхолдер (человек, роль или отдел), визуально разграничивающий распределение обязанностей и ответственности за подпроцессы бизнес-процесса. Дорожка может располагаться как горизонтально, так и вертикально.
В чем отличия? Блок-схема против блок-схемы Swimlane
Блок-схема дорожек отличается от других блок-схем тем, что процессы и решения визуально сгруппированы путем размещения их на дорожках. Параллельные линии делят диаграмму на дорожки, по одной дорожке для каждого человека, группы или подпроцесса. Дорожки помечены, чтобы показать, как организована диаграмма.
В приведенном ниже примере вертикальное направление представляет собой последовательность событий в общем процессе, а горизонтальные деления показывают, какой подпроцесс выполняет этот шаг. Стрелки между дорожками показывают, как информация или материал передаются между подпроцессами.
С другой стороны, поток можно повернуть так, чтобы последовательность читалась по горизонтали слева направо, при этом задействованные роли показаны на левом краю. Это может быть легче читать и проектировать, поскольку экраны компьютеров обычно шире, чем в высоту, что дает лучшее представление о потоке.
Блок-схема развертывания Swimlane
Формы, используемые при рисовании блок-схемы развертывания, такие же, как и в стандартной блок-схеме с обозначениями дорожек. Блок-схема развертывания сочетает в себе две ключевые функции:
- Последовательность шагов в процессе
- Кто отвечает за какой этап развертывания
Он показывает этапы процесса, а также показывает, какое лицо или группа вовлечены в реакцию на шаг. В приведенном ниже примере показаны ответственные группы, перечисленные вверху. Это группы Производство, Администрация и Маркетинг. Вы можете нарисовать блок-схему развертывания, в которой перечислены люди, а не группы. Преимущество блок-схемы развертывания заключается в том, что она показывает, где работа передается от одного человека или группы к другому, где недоразумения и ошибки могут быть сведены к минимуму.
Блок-схема дорожки возможностей
Блок-схемы возможностей (также известные как блок-схемы добавленной стоимости) используются для определения того, какие шаги в процессе являются дополнительными или расточительными. Он отделяет эти важные шаги для создания продукта или услуги от дополнительных затрат.
Блок-схемы алгоритмов. Назначение блоков данных
В статье пойдет разговор о том, что такое схема алгоритмов, какие данные в эту схему вносятся. Также будет дан ответ на вопрос, какие существуют виды блоков для схем представления алгоритма.
Algorithm — строгая последовательность действий для какого-нибудь исполнителя, которая приводит к решению поставленной задачи либо получению заданного результата за определенное количество число шагов. Упоминание исполнителя здесь неслучайно, ведь любая алгоритмическая последовательность создается с учетом конкретного исполнителя и имеющихся у него возможностей. Под исполнителем понимается некий субъект, который способен понять и выполнить определенный перечень команд. Совокупность этих команд является системой команд исполнителя.
Но чтобы выполнить алгоритм, одного лишь его наличия недостаточно. Выполнение предполагает применение в контексте решения реальной задачи, а значит, потребуется выполнение запланированных действий по отношению к конкретным входным данным. Следовательно, исполнителю надо передать входные данные до начала алгоритма:
Входные данные → Algorithm → Выходные данные (результат)
Когда исполнитель получает выходные данные, они выдаются в качестве результата выполненной работы. Также стоит учесть, что в процессе выполнения этой самой работы возможно создание и использование в программе промежуточных данных.
Блок-схемы алгоритма
Наглядным способом представления алгоритмической последовательности является блочная схема. Она выглядит как последовательность функциональных блоков, связанных между собой. Каждый из этих элементов отвечает за выполнение одного либо нескольких действий. Так как возможны разные действия, то каждому типу действия соответствует геометрическая фигура.
Очередность выполнения действий определяется линиями, которые соединяют блочные элементы с данными. Принято, чтобы компоненты схемы соединялись слева направо и сверху вниз. В случае наличия какой-либо иной последовательности, используют линии направленного вида (со стрелками).
Блок–схемы алгоритма: виды и примеры
Функциональный (операторный) блок:
Его еще называют процессом. Такой элемент нужен для указания действия (шага) алгоритма. Он представляет собой прямоугольник, в который может входить одна направленная линия и выходить тоже одна линия. Внутри записывают команду, подлежащую выполнению. Для наглядности возможна запись нескольких команд в одном блочном элементе.
Альтернативный блок:
Это условный блок, т. к. в нем прописывается какое-нибудь условие. Он указывает наличие выбора среди одного из двух вероятных действий. Геометрическая фигура представляет собой ромб. Внутри прописывается условие выбора (вопрос, сравнение). В качестве условия может выступать выражение, для которого справедливо лишь одно из 2-х значений: «ложь» либо «истина».
В ромб может входить одна направленная линия, а выходить две направленные линии, причем одна подписывается словом «Да», вторая — «Нет». В случае, если записанное внутри геометрической фигуры условие является верным (значение истинно), управление передается по стрелке, которая подписана словом «Да». В обратной ситуации управление переходит на стрелку «Нет».
Блок начала/конца (пуск/останов):
Применяется, соответственно, в начале и конце блок-схемы алгоритма.
Блок ввода-вывода:
С его помощью организуют ввод исходных данных и вывод результирующих данных.
Блок цикла:
Служит для организации циклического процесса с каким-нибудь параметром. Должно быть известно как число итераций (повторений) цикла, так и шаг изменения параметра. Внутри через запятую прописывается начальное значение циклического параметра, а также шаг изменения и конечное значение.
Блок подпрограммы (предопределенного процесса):
Применяется в целях указания обращения к отдельным модулям, библиотечным подпрограммам, вспомогательным алгоритмам.
Элемент печати:
Обозначает вывод результатов на печать.
Исходя из вышесказанного, пример простейшей блок-схемы алгоритма (речь идет о линейной последовательности) будет выглядеть следующим образом:
Следующий пример представляет собой схематическое описание (блок-схему) итога работы алгоритма целочисленных преобразований с оператором присваивания := :