Блок схема алгоритма цикл гост

Схема – это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени – чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.

На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт – ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

Содержание:

1. Элементы блок-схем алгоритмов
2. Примеры блок-схем
3. Нужны ли блок-схемы? Альтернативы

Элементы блок-схем алгоритмов

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

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

Примеры блок-схем

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

Сортировка вставками

Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.

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

Блок-схема алгоритма сортировки вставками

В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны – алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того.

На блок-схеме показано каким образом может использоваться символ перехода – его можно использовать не только для соединения частей схем, размещенных на разных листах, но и для сокращения количества линий. В ряде случаев это позволяет избежать пересечения линий и упрощает восприятие алгоритма.

Сортировка пузырьком

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

Блок-схема алгоритма сортировки пузырьком

На блок-схеме показано использование символов начала и конца цикла. Условие внешнего цикла (А) проверяется в конце (с постусловием), он работает до тех пор, пока переменная hasSwapped имеет значение true. Внутренний цикл использует предусловие для перебора пар сравниваемых элементов. В случае, если элементы расположены в неправильном порядке, выполняется их перестановка посредством вызова внешней процедуры (swap). Для того, чтобы было понятно назначение внешней процедуры и порядок следования ее аргументов, необходимо писать комментарии. В случае, если функция возвращает значение, комментарий может быть написан к символу терминатору конца.

Сортировка выбором

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

Блок-схема сортировки выбором

На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива, поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort, … .

На блоге можно найти другие примеры блок-схем:

• блок-схема проверки правильности расстановки скобок арифметического выражения [2];
• блок-схемы алгоритмов быстрой сортировки и сортировки слиянием [3].

Часть студентов традиционно пытается рисовать блок-схемы в 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].

Список использованных источников:

1. ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документа­ции».
2. Алгоритм. Свойства алгоритма https://pro-prof.com/s/578
3. Алгоритмы сортировки слиянием и быстрой сортировки https://pro-prof.com/s/813
4. yEd Graph Editor https://www.yworks.com/products/yed
5. Книги: алгоритмы https://pro-prof.com/books-algorithms
6. Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник. -СПб.: Питер, 2002. -656 с.
7. Кент Бек Экстремальное программирование: разработка через тестирование – СПб.: Питер – 2003
8. Визуальный язык ДРАКОН https://drakon.su/
9. Шилов Н.В. Верификация шаблонов алгоритмов для метода отката и метода ветвей и границ. Моделирование и анализ информационных систем, ISSN 1818 – 1015, т.18, №4, 2011
10. Брукс Ф., Мифический человеко – месяц или как создаются программные системы. СПб. Символ Плюс, 1999 – 304 с. ил.

Источник