Символ начало и конец цикла
Примеры построения алгоритмов
ПРИМЕНЕНИЕ СИМВОЛОВ
| Символ | Наименование символа | |||||
| Символы данных | ||||||
| Основные | Данные | + | + | + | + | + |
| Запоминаемые данные | + | – | + | + | + | |
| Специфические ОЗУ | + | – | + | + | + | |
| ЗУ с послед. выборкой | + | – | + | + | + | |
| ЗУ с прямым доступом | + | – | + | + | + | |
| Документ | + | – | + | + | + | |
| Ручной ввод | + | – | + | + | + | |
| Карта | + | – | + | + | + | |
| Бумажная лента | + | – | + | + | + | |
| Дисплей | + | – | + | + | + | |
| Символы процесса | ||||||
| Основные | Процесс | + | + | + | + | + |
| Специфические | Предопределенный процесс | – | + | + | + | – |
| Ручная операция | + | – | + | + | – | |
| Подготовка | + | + | + | + | – | |
| Решение | – | + | + | – | – | |
| Параллельные действия | – | + | + | + | – | |
| Граница цикла | – | + | + | – | – | |
| Символы линий | ||||||
| Основные | Линия | + | + | + | + | + |
| Специфические | Передача управления | – | – | – | + | – |
| Канал связи | + | – | + | + | + | |
| Пунктирная линия | + | + | + | + | + | |
| Специальные символы | Соединитель | + | + | + | + | + |
| Терминатор | + | + | + | – | – | |
| Комментарий | + | + | + | + | + | |
| Пропуск | + | + | + | + | + |
Примечание. Знак “+” указывает, что символ используют в данной схеме, знак “-” – не используют.
1 – Схема данных;
2 – Схема программы;
3 – Схема работа системы;
4 – Схема взаимодействия программ;
5 – Схема ресурсов системы;
ОЗУ – оперативное запоминающее устройство;
ЗУ – запоминающее устройство.
Алгоритмы бывают: линейные, разветвляющиеся, циклические.
| Данные. Символ отображает данные, носитель данных не определен. |
| Процесс. Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться). |
| Подготовка. Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последовательную функцию (установка переключателя, модификация индексного регистра или инициализация программы). |
| Решение. Символ отображает решение или функцию переключаемого типа, имеющую один вход и ряд альтернативных выходов, один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. |
| Граница цикла. Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или конце в зависимости от расположения операции, проверяющей условие. |
| Линия. Символ отображает поток данных или управления. |
| Терминатор. Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных). |
| Комментарий. Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. |
| Пропуск. Символ (три точки) используют схемах для отображения пропуска символа или группы символов, в которых не определены ни тип, ни число символов. Символ используют только в символах линий или между ними. Он применим равным образом в схемах, изображающих общие решения с неизвестным числом повторений. |
Циклический алгоритм может представлен в виде следующих основных структур:
– цикл – ДО ;
– цикл – ПОКА ;
– цикл с параметром.
Цикл – ДО начинается с выполнения тела цикла, затем проверяется условие окончания цикла, таким образом тело цикла обязательно будет реализовано хотя бы один раз. Такую разновидность цикла еще называют циклом с постусловием. В стандартном виде цикл выполняется до тех пор пока условие не станет истинным.
Словесная запись соответствующего цикла может быть определена как: повторять тело цикла до выполнения заданного условия. Графически данная конструкция может быть представлена:
а) с использованием блока решение;
б) с использованием блоков начало и конец цикла
а) Цикл – ДО с блоком решения (устаревшая конструкция алгоритма)
б) Цикл – ДО с блоками начало и конец цикла
Цикл – ПОКА начинается с проверки условие окончания цикла, поэтому такую разновидность цикла называют еще циклом с предусловием. Стандартно цикл выполняется только в том случае, когда условие истинно. В частности, может оказать, что тело цикла не будет выполнено ни разу если с самого начала условие продолжения цикла не выполнялось. Словесная запись соответствующего цикла может быть определена как: пока выполняется заданное условие выполнять тело цикла.
Графически данная конструкция может быть представлена:
а) с использованием блока решение;
б) с использованием блоков начало и конец цикла.
а) Цикл – ПОКА с блоком решение
б) Цикл – ПОКА с блоками начало и конец цикла
Для того чтобы не происходило “зацикливание” (бесконечное повторение тела цикла), необходимо, чтобы в теле цикла осуществлялись преобразования, приводящие к изменению параметра входящего в условие завершения цикла. Цикл с параметром представляет собой такую управляющую структуру, которая используется в тех случаях, когда тело цикла выполняется при каждом значении некоторого параметра, изменяющегося в заданных пределах с заданным шагом, т.е. количество циклов заранее известно.
Словесная запись такой структуры может выглядеть так: для каждого параметра i , изменяющегося от A до B с шагом C, выполнять тело цикла.
Графически данная конструкция может быть представлена с использованием символа подготовка:
Рассмотренный цикл параметром еще называют арифметическим циклом, если шаг изменения параметра равен единице, то его можно не указывать.
Примеры построения алгоритмов:
Задача 1. Вычислить сумму n первых десяти членов прогрессии , где K и i соответственно значение и номер члена
прогрессии.
Задача 2. Определить количество первых членов прогрессии , сумма которых не превышает заданное число A, где K и i соответственно значение и номер члена прогрессии.
2. Описание практической части работы:
2.1. Цели лабораторной работы: Изучить построение циклических алгоритмов, решить задачу с помощью организации арифметических и логических циклов.
2.2. Постановка задачи: В соответствии с номером варианта найти значение функции, заданной одним или несколькими математическими выражениями.
2.3. Порядок выполнения работы:
2.3.1. Ознакомиться с теоретической частью.
2.3.2. Получить задание у преподавателя.
2.3.3. Выполнить работу.
2.3.4. Оформить отчет:
2.3.4.1. Содержание отчета:
1. Цель работы – краткая формулировка поставленной цели.
2. Порядок выполнения – определяются действия, необходимые для выполнения данной работы.
3. Постановка задачи – формулирование задачи в соответствии с индивидуальным заданием.
4. Решение поставленной задачи:
4.1. Математическое описание решения поставленной задачи содержит описание связей между параметрами с использованием принятых в математике обозначений.
4.2. Описание логической структуры программы (алгоритм решения) содержит:
– краткое описание схемы программы,
– алгоритм решения (по ГОСТ ) – рисунок,
– краткое описание используемых операторов языка программирования (при необходимости).
4.3. Описание программы содержит:
· название файла, его размер,
· текст программы (или фрагмент для решения конкретной, наиболее важной части задания).
4.4. Результат работы программы:
– значения, полученные в результате выполнения программы
– анализ полученных результатов.
Выводы – отвечают на поставленную цель.
2.4. Контрольные вопросы:
1. Дайте определение алгоритма ?
2. Назовите свойства алгоритмов?
3. Каким образом можно описать алгоритм решения задачи ?
4. Чем характеризуется циклическая структура алгоритма ?
5. Каким образом отображается циклическая структура алгоритма на блок-схеме ?
6. Чем отличается цикл ДО от цикла ПОКА ?
7. Как изображается в схеме программы логический цикл ?
8. Какой из циклов эффективнее (быстрее выполняется в программе) логический или арифметический ?
9. Когда предпочтительнее использовать арифметический цикл в программе, написанной на языке Basic Microsoft ?
10. Что такое пустой цикл и зачем он бывает нужен в программе ?
Таблица
Задания для разработки циклических алгоритмов
Источник
Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.
Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.
Содержание:
- Элементы блок-схем алгоритмов
- Примеры блок-схем
- Нужны ли блок-схемы? Альтернативы
Элементы блок-схем алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.
Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов, но в текущей статье они, как и ряд специфических символов, не рассматриваются. Рассмотрены лишь основные символы, которых всегда достаточно студентам.
Терминатор начала и конца работы функции | Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора. |
Операции ввода и вывода данных | В ГОСТ определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях. |
Выполнение операций над данными | В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций. |
Блок, иллюстрирующий ветвление алгоритма | Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения — «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах — значения этой переменной. |
Вызов внешней процедуры | Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями. |
Начало и конец цикла | Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня — оператор с предусловием (while) или постусловием (do … while). |
Подготовка данных | Символ «подготовка данных» в произвольной форме (в ГОСТ нет ни пояснений, ни примеров), задает входные значения. Используется обычно для задания циклов со счетчиком. |
Соединитель | В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно. |
Комментарий | Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией. |
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
На каждом шаге алгоритма выбирается первый элемент необработанной части массива и вставляется в отсортированную так, чтобы в ней сохранялся требуемый порядок следования элементов. Вставка может выполняться как в конец массива, так и в середину. При вставке в середину необходимо сдвинуть все элементы, расположенные «правее» позиции вставки на один элемент вправо. В алгоритме используется два цикла — в первом выбираются элементы необработанной части, а во втором осуществляется вставка.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (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].
Список использованных источников:
- ГОСТ 19.701–90 (ИСО 5807–85) «Единая система программной документации».
- Алгоритм. Свойства алгоритма https://pro-prof.com/archives/578
- Алгоритмы сортировки слиянием и быстрой сортировки https://pro-prof.com/archives/813
- yEd Graph Editor https://www.yworks.com/products/yed
- Книги: алгоритмы https://pro-prof.com/books-algorithms
- Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник. -СПб.: Питер, 2002. -656 с.
- Кент Бек Экстремальное программирование: разработка через тестирование – СПб.: Питер – 2003
- Визуальный язык ДРАКОН https://drakon.su/
- Шилов Н.В. Верификация шаблонов алгоритмов для метода отката и метода ветвей и границ. Моделирование и анализ информационных систем, ISSN 1818 – 1015, т.18, №4, 2011
- Брукс Ф., Мифический человеко — месяц или как создаются программные системы. СПб. Символ Плюс, 1999 — 304 с. ил.
Источник