Способ кодирования блок схемы
8.2. Блок-схемы алгоритмов
При описании алгоритмов давно и успешно используются блок-схемы (Basic Flowchart). Построение блок-схем алгоритмов регламентируется ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации. Схемы алгоритмов программ, данных и систем. Условные обозначения и правила выполнения» [22]. Данный государственный стандарт составлен на основе международного стандарта «ISO 5807-85. Information processing – Documentation symbols and conventions for data, program and system flowcharts, program network charts and system resources charts».
Согласно ГОСТ 19.701-90 под схемой понимается графическое представление определения, анализа или метода решения задачи. С помощью схем можно отобразить как статические, так и динамические аспекты системы. Символы, приведенные в государственном стандарте, могут использоваться в следующих типах схем:
— схемы данных – определяют последовательность обработки данных и их носители;
— схемы программ – отображают последовательность операций в программе (по сути, это и есть блок-схемы алгоритмов в традиционном понимании);
— схемы работы системы – отображают управление операциями и потоки данных в системе;
— схемы взаимодействия программ – отображают путь активации программ (модулей) и их взаимодействие с соответствующими данными;
— схемы ресурсов системы – отображают конфигурацию блоков данных и обрабатывающих блоков.
Как видно из приведенных выше типов схем, они могут использоваться не только для моделирования поведенческого аспекта, но и для задач функционального, информационного и компонентного проектирования.
По своему назначению символы (элементы) графической нотации делятся на четыре категории:
— символы данных – указывают на наличие данных, вид носителя или способ ввода-вывода данных;
— символы процесса – указывают операции, которые следует выполнить над данными;
— символы линий – указывают потоки данных между процессами и/или носителями данных, а также потоки управления между процессами;
— специальные символы – используются для облегчения написания и чтения схем.
Кроме деления по смысловому содержанию (назначению), каждую категорию символов (кроме специальных) делят на основные и специфические символы. Основной символ используется в тех случаях, когда точный вид процесса или носителя данных неизвестен или отсутствует необходимость в описании фактического носителя данных (процесса). Специфический символ используется в тех случаях, когда известен точный вид процесса или носителя данных и это необходимо отобразить на схеме. В следующей таблице приведены элементы графической нотации блок-схем.
Таблица 8.1. Условные обозначения на блок-схемах
| № п/п | Символ | Наименование | Назначение | |
| 1. СИМВОЛЫ ДАННЫХ Основные | ||||
| 1.1 | Данные | Данные, носитель которых не определен. | ||
| 1.2 | Запоминающее устройство (ЗУ) | Данные, хранимые в виде, пригодном для автоматической обработки, носитель не определен. | ||
| Специфические | ||||
| 1.3 | ОЗУ | Данные, хранящиеся в ОЗУ (оперативная память). | ||
| 1.4 | ЗУ с последовательным доступом | Данные, хранящиеся на магнитной ленте (магнитная лента, магнитофонная кассета). | ||
| 1.5 | ЗУ с прямым доступом | Данные, хранящиеся на жестких или гибких магнитных дисках, CD, DVD, ZIP, флеш-накопителях и т.д. | ||
| 1.6 | Документ | Данные, представляемые не в компьютерном виде (на бумаге, на пленках и т.д.). | ||
| 1.7 | Ручной ввод | Данные, вводимые вручную с помощью клавиатуры, мыши, светового пера и т.д. | ||
| 1.8 | Карта | Данные на перфокартах, картах с магнитной полосой, смарт-картах, картах со считываемыми метками и т.д. | ||
| 1.9 | Бумажная лента | Данные на бумажной ленте. | ||
| 1.10 | Дисплей | Данные, отображаемые на экране монитора, сигнальные индикаторы и т.д. | ||
| 2. СИМВОЛЫ ПРОЦЕССА Основной | ||||
| 2.1 | Процесс | Операция или группа операций (функций, действий) по обработке данных. | ||
| Специфические | ||||
| 2.2 | Предопределенный процесс (процедура) | Процесс, состоящий из одной или нескольких операций, определенных в другой подпрограмме (применительно к блок-схемам — описанных на другой схеме). | ||
| 2.3 | Ручная операция | Операция, выполняемая вручную. | ||
| 2.4 | Подготовка | Подготовительные операции, выполняемые с целью модификации последующих операций (цикл с параметром For-To-Do). | ||
| 2.5 | Решение | Операция с одним входом и несколькими альтернативными выходами, один из которых активизируется после проверки условия, записываемого внутри символа (операторы ветвления — If-Then-Else, Case или Switch). | ||
| 2.6 | Параллельные действия | Параллельное выполнения двух и более операций. | ||
| 2.7 | Границы цикла | Начало и конец цикла. Особенности работы цикла (инициализация, приращение, условие) записывается в начале или конце, в зависимости от того, где осуществляется его проверка (циклы с пред- или постусловием — For-To-Do, While-Do, Do-While или Repeat-Until). | ||
| 3. СИМВОЛЫ ЛИНИЙ Основной | ||||
| 3.1 | Линия | Поток данных или управления. | ||
| Специфические | ||||
| 3.2 | Канал связи | Передача данных по каналу связи. | ||
| 3.3 | Пунктирная линия | Альтернативная связь между двумя и более символами или для обводки комментируемого участка схемы. | ||
| 4. СПЕЦИАЛЬНЫЕ СИМВОЛЫ | ||||
| 4.1 | ГОСТ | Соединитель | Используется для обрыва линий и их продолжения в другом месте. Обычно используется для обозначения взаимосвязанных частей схемы на разных листах. Внутри соединителя пишется номер соединения. | |
| ИСО | ||||
| 4.2 | Терминатор | Выход во внешнюю среду или вход из внешней среды (начало и конец процесса обработки данных [в этом случае внутри пишут «начало» или «конец»], источник или пункт назначения данных, начало и конец работы предопределенного процесса). | ||
| 4.3 | Получатель – отправитель | По назначению аналогичен символу «Терминатор». | ||
| 4.4 | Комментарий | Символ используется для внесения пояснительных записей. | ||
| 4.5 | Пропуск | Пропуск символа или группы символов. | ||
8.3. Правила и рекомендации построения блок-схем
Ниже приводятся некоторые правила и рекомендации построения схем [22].
1. Допускается зеркально отображать символы и поворачивать их вокруг оси. В частности, запоминающие устройства с прямым доступом (таблицы на жестком диске) на схемах, как правило, поворачивают на 90 о против часовой стрелки.
2. Большинство символов допускают задание внутри них текстовых пояснений. Если текст не помещается внутри символа, то лучше его приводить, используя комментарии.
3. Количество пересечений линий следует минимизировать. При этом считается, что пересекающиеся линии не имеют логической связи друг с другом. Другими словами потоки данных или управления в местах пересечений не меняют своего направления.
4. Если две или более линий объединятся в одну, то место объединения должно быть смещено.
Рис. 8.1. Объединение потоков данных или управления
5. Несколько выходов из символа решения следует показывать одним из следующих способов:
— несколькими линиями от данного символа к другим символам;
— одной линией от данного символа, которая затем разветвляется в соответствующее число потоков.
Рис. 8.2. Ветвление линий
В случае ветвления каждый выход из символа должен сопровождаться либо записью условия (например, условие «Сравнить A и B», 3 выхода: A > B, A
Источник
Блок-схемы алгоритмов. ГОСТ. Примеры
Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.
Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.
Содержание:
Элементы блок-схем алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.
Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов, но в текущей статье они, как и ряд специфических символов, не рассматриваются. Рассмотрены лишь основные символы, которых всегда достаточно студентам.
Терминатор начала и конца работы функции
Операции ввода и вывода данных
Выполнение операций над данными
Блок, иллюстрирующий ветвление алгоритма
Вызов внешней процедуры
Начало и конец цикла
Подготовка данных
Соединитель
Комментарий
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
На каждом шаге алгоритма выбирается первый элемент необработанной части массива и вставляется в отсортированную так, чтобы в ней сохранялся требуемый порядок следования элементов. Вставка может выполняться как в конец массива, так и в середину. При вставке в середину необходимо сдвинуть все элементы, расположенные «правее» позиции вставки на один элемент вправо. В алгоритме используется два цикла — в первом выбираются элементы необработанной части, а во втором осуществляется вставка.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (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].
Источник
