12 графическое представление структурированных схем алгоритмов

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок «модификация» используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

Блок «предопределенный процесс» используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам.

Источник

Занятие 1. Понятие блок-схемы. Основные виды блоков

Блок-схема – это графическая реализация алгоритма.

Блок-схема представляет собой удобный и наглядный способ записи алгоритма.

Блок-схема состоит из функциональных блоков разной формы, связанных между собой стрелками. В каждом блоке описывается одно или несколько действий. Основные виды блоков представлены в табл. 2.1.

Таблица 2.1. Виды блоков

Форма блока	Назначение блока
	начало и конец блок-схемы
	блок ввода данных
	блок выполнения действия
	блок условия
	блок вывода данных

Любая команда алгоритма записывается в блок-схеме в виде графического элемента – блока, и дополняется словесным описанием. Блоки в блок-схемах соединяются линиями потока информации. Направление потока информации указывается стрелкой. В случае потока информации сверху вниз и слева направо стрелку ставить не обязательно. Блоки в блок-схеме имеют только один вход и один выход (за исключением логического блока – блока с условием).

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

Математические выражения и логические высказывания должны быть описаны математическим языком, т.к. блок-схема не должна иметь привязки к какому-то определенному языку программирования. Одна и таже блок-схема может быть реализована в программах на разных языках программирования. К примеру, функция в блок-схеме будет выглядеть таким образом: , а не таким образом: .

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

Источник

Многие специалисты в области теории программирования считают, что графическое представление алгоритмов в соответствии с ГОСТ 19.701-90 ( ISO 5807-85 , см. п. 2.2.2) скрывают структуру структурированной программы,

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

В данном пособии рассмотрены два из них – метод Дамке и диаграммы Насси-Шнейдермана.

3.4.1. Метод Дамке

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

Три основных конструкции структурного программирования изображаются следующим образом.

1) Функциональный блок по-прежнему обозначается прямоугольником

Рисунок 3.19 – Представление функционального блока по методу Дамке

2) Конструкция If-Then-Else изображается так, как иллюстрирует рисунок 3.20.

Элементы с выполняемыми действиями находятся справа от символа «Решение». Вход и выход из конструкции находятся соответственно сверху и снизу символя «Решение».

3) Конструкция Do-While (цикл с предусловием “Пока”) изображается так, как показывает рисунок 3.21.

Тело цикла выполняется до тех пор, пока условие истинно. Условие проверяется первым. Графически это изображается положением шестиугольника над выполняемым телом цикла.

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

Рисунок 3.20 – Представление конструкции If-Then-Else

Рисунок 3.21 – Представление конструкции Do-While по методу Дамке

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

1) Конструкция Repeat-Until (цикл с постусловием “До”) изображается так, как иллюстрирует рисунок 3.22.

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

Рисунок 3.22 – Представление конструкции Repeat-Until по методу Дамке

2) Конструкция цикла с параметром изображается так, как представляет рисунок 3.23.

3) Конструкция Case изображается так, как иллюстрирует рисунок 3.24.

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

Элементы в самой левой части схемы представляют укрупнённую структуру алгоритма. Затем элементы расширяются вправо по мере разделения каждого элемента на подзадачи.

Чтобы исследовать любую подзадачу, достаточно анализировать только те элементы и управляющие структуры, которые находятся справа от данной подзадачи.

Источник

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

Графическое представление (блок-схема) алгоритма — это на­бор специальных графических символов, расположенных в по­рядке выполнения действий алгоритма.

Для этого способа записи алгоритмов используются стандар­тизованные графические обозначения (символы).

Начало алгоритма обозначается знаком

Идущая вниз линия означает переход к первому действию ал­горитма. Таким же знаком обозначается и конец алгоритма, к ко­торому линия от последнего символа подходит сверху:

Любое действие алгоритма изображается прямоугольником, в который обычно вписывают название действия:

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

Проверка выполнения условия и выбор ветви алгоритма, соот­ветствующей выполнению или невыполнению условия, представ­ляются ромбом, в который условие вписывается в виде вопроса. При выполнении условия переход к нужной ветви происходит в

направлении ответа «Да», а если условие не выполнено — в на­правлении ответ «Нет»:

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

Символ вызова вспомогательного алгоритма имеет вид

Есть и другие символы для обозначения различных операций в алгоритме.

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

Символ вызова вспомогательного алгоритма имеет вид

Составим блок-схемы некоторых из рассмотренных ранее ал­горитмов. Блок-схемы двух алгоритмов с ветвлением — «Взять хлеб» и сортировки изделий — приведены на рис. 2.1, 2.2. Они наглядно показывают преимущество графического представления алгорит­мов — легко прослеживается последовательность действий как при выполнении, так и при невыполнении проверяемого условия.

На рис. 2.3 представлена блок-схема циклического алгоритма, являющегося развитием алгоритма сортировки изделий. Предыду­щий алгоритм представляет собой цикл, который повторяется при положительном результате проверки условия наличия изделий на конвейере.

На блок-схеме хорошо видны границы цикла — он охвачен линией, которая поднимается вверх, противоположно стандарт­ному направлению перехода от символа к символу, и заканчива­ется стрелкой. После выполнения цикла происходит возврат по этой линии к первому действию цикла, в данном случае к про­верке наличия изделий на конвейере.

Линия возврата фактически заменяет строку Конец цикла, ог­раничивающую цикл снизу при словесном описании алгоритма,

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

В этом алгоритме проверка условия производится до начала цикла и возможна ситуация, когда цикл не исполнится ни разу: если изделий на конвейере нет, то проверка условия сразу выво­дит на окончание цикла.

Рассмотрим блок-схему циклического алгоритма погрузки кон­тейнеров из подразд. 2.2.3, где проверка условия повторения цик­ла производится после его исполнения (рис. 2.4). Вслед за симво­лом Начало следуют действия алгоритма, поэтому цикл исполня­ется всегда, как минимум, один раз. Если погрузка контейнера

привела к отсутствию свободного места в вагоне, то проверка ус­ловия сразу выводит на символ Конец. Линия возврата по-прежне­му охватывает цикл, указывая его нижнюю и верхнюю границы.

Блок-схема расширенного варианта этого алгоритма, содержа­щего условия, проверяемые как до, так и после выполнения ко­манд цикла (см. подразд. 2.2.3), показана на рис. 2.5. Проследите по этому рисунку ход исполнения алгоритма при различных комби­нациях условий наличия свободного места в вагоне и наличия контейнеров для погрузки.

Рассмотрим блок-схемы вспомогательных алгоритмов. У алго­ритма, используемого в качестве вспомогательного, есть одна осо­бенность: в нем производятся действия с информацией, передан­ной ему из основного алгоритма, и туда же при необходимости сообщается результат выполнения вспомогательного алгоритма. Поэтому блок-схема вспомогательного алгоритма содержит сим­вол ввода данных, а при необходимости — и символ вывода ре­зультатов, что подчеркивает взаимодействие вспомогательного алгоритма с основным.

На рис. 2.6 приведена блок-схема алгоритма «Нагрев до t». Сим­вол ввода данных указывает на получение из основного алгорит­ма значения температуры нагрева t. После выполнения алгоритма нагрева продолжается выполнение основного алгоритма с дей-

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

Алгоритмический язык

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

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

Последовательность действий должна четко выражаться после­довательностью команд, а поскольку додумывать и догадываться машина не умеет, каждому шагу алгоритма (например, анализу выполнения какого-то условия) должна соответствовать четко понимаемая машиной команда.

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

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

Служебные слова — это обычные слова нашего языка, но их запись в алгоритмическом языке однозначна и никакие другие варианты записи этих слов недопустимы. Например, если вы пи­шете адрес на конверте, вы можете написать: «город Пенза», или «гор. Пенза», или «г. Пенза». Если бы слово «город» входило в спи­сок служебных слов алгоритмического языка, то его всегда нужно было бы писать только в одном виде (например: «гор.»). Даже точ­ка после сокращения слова должна быть особо оговорена — ста­вить ее или нет.

Перед названием каждого алгоритма, записанного на алгорит­мическом языке, ставится служебное слово АЛГ (буквы заглав­ные, без точки). Для указания начала и конца алгоритма исполь­зуются служебные слова НАЧ и КОН. Каждый шаг алгоритма за­писывается отдельной строкой.

Общий вид линейного алгоритма на алгоритмическом языке:

Угловые скобки означают, что в данной строке должно быть записано то, что указано в этих скобках.

Для записи алгоритмов с ветвлением используются служебные слова ЕСЛИ, ТО, ИНАЧЕ, ВСЕ (конец ветвления). Общий вид ветвления:

Запишем на алгоритмическом языке алгоритм, блок-схема ко­торого приведена на рис. 2.2.

АЛГ «Алгоритм сортировки изделий» НАЧ

поместить изделие в измерительное устройство

измерить диаметр изделия ЕСЛИ диаметр больше заданного ТО

поместить изделие в магазин № 1 ИНАЧЕ

поместить изделие в магазин № 2 ВСЕ КОН

Бывает так, что после строки ИНАЧЕ в алгоритме с ветвлени­ем располагается не действие, а новое условие. Тогда это второе условие вводится не в отдельной строке ЕСЛИ, а в той же строке, в которой находится ИНАЧЕ:

Последнее ИНАЧЕ относится к условию 2, т.е. соответствует невыполнению этого условия. Сочетание служебных слов ИНАЧЕ ЕСЛИ часто заменяют служебным словом ИНЕС.

В циклических алгоритмах используются служебные слова ПОКА, ЦИКЛ, КЦИКЛ (конец цикла). Общий вид циклического участка алгоритма:

Запишем циклический алгоритм сортировки изделий, блок-схема которого приведена на рис. 2.3. Судя по блок-схеме, это алгоритм с предусловием. Поэтому верхней границей цикла явля­ется условие Есть изделия на конвейере! Далее следуют действия цикла, а расположение нижней границы КЦИКЛ показывает ли­ния возврата. Имеющееся в алгоритме ветвление входит в цикл и заканчивается перед концом цикла. Для удобства чтения алгорит­ма действия, образующие цикл, сдвигаются при записи вправо — так цикл легче увидеть. Аналогично можно сдвинуть участок с ветвлением. Алгоритм записывается в порядке продвижения по блок-схеме и выглядит следующим образом:

АЛГ «Циклический алгоритм сортировки изделий» НАЧ

ПОКА есть изделия на конвейере

поместить изделие в измерительное устройство

ЕСЛИ диаметр больше заданного ТО

поместить изделие в магазин № 1 ИНАЧЕ

поместить изделие в магазин № 2 ВСЕ КЦИКЛ

Рассмотрим последовательность действий в этом алгоритме. Пока предусловие Есть изделия на конвейере не нарушено, выполняется измерение диаметра изделия и оно помещается в магазин № 1 или № 2. Служебное слово ВСЕ означает конец ветвления, после которого следует переходить к следующей строке алгоритма. В ней помещено слово КЦИКЛ (конец цикла), требующее возврата к

началу цикла, т.е. к строке ПОКА, после чего цикл повторится. Когда условие в строке ПОКА нарушится, по правилам выполне­ния циклических алгоритмов надо будет перейти к строке, следу­ющей за указателем конца цикла КЦИКЛ (в нашем случае — это строка КОН), и выполнение алгоритма заканчивается.

Запишем на алгоритмическом языке более сложный алгоритм (см. рис. 2.5).

В этом алгоритме, как видно из блок-схемы, есть и предусло­вие (Есть контейнер для погрузки?), и постусловие (В вагоне есть свободное место?), поэтому в нем сочетаются записи в виде ПОКА. КЦИКЛ и в виде ЦИКЛ . ПОКА.

Первый элемент блок-схемы при продвижении от начала алго­ритма — линия возврата, идущая от символа постусловия. В алго­ритмах с постусловием она указывает место, с которого возоб­новляется цикл при его повторении. В алгоритмическом языке это место обозначается служебным словом ЦИКЛ.

Далее расположен графический элемент предусловия, вводи­мого словом ПОКА, после которого идет последовательность дей­ствий вплоть до постусловия. Постусловие тоже вводится служеб­ным словом ПОКА. Если условие выполнено, то в алгоритмах с постусловием следует возврат к строке ЦИКЛ, а если не выпол­нено — переход к следующей за постусловием строке (в нашем случае — к окончанию алгоритма КОН).

Все это происходит, если не нарушено предусловие Есть кон­тейнер для погрузки. Когда же это условие нарушено, в алгоритмах с предусловием происходит переход к строке, следующей за ука­зателем конца цикла КЦИКЛ (в нашем случае — к окончанию алгоритма КОН).

В итоге этот алгоритм на алгоритмическом языке записывается следующим образом:

АЛГ «Алгоритм погрузки контейнеров» НАЧ

ПОКА есть контейнер для погрузки

поднять очередной контейнер

переместить контейнер к вагону

погрузить контейнер в вагон

вернуть кран в исходное положение ПОКА в вагоне есть свободное место КОН

Сдвиг строк при записи позволяет легко сориентироваться, где начинается и заканчивается цикл ПОКА. КЦИКЛ, а где ЦИКЛ. ПОКА.

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

Так как в основном алгоритме вызов вспомогательного алго­ритма производится простым указанием его заголовка, то общий вид основного алгоритма на алгоритмическом языке может быть, например, следующим:

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

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

Контрольные вопросы

1. Сформулируйте понятие алгоритма.

2. В чем особенность восприятия алгоритмов машинами?

3. Дайте определение программы.

4. Назовите виды алгоритмов.

5. Что такое линейный алгоритм? Приведите пример.

6. Что такое условный алгоритм? Приведите пример.

7. Что такое циклический алгоритм? Приведите пример.

8. Что такое вспомогательный алгоритм? Приведите пример.

9. Расскажите о способах записи алгоритмов.

10. Изобразите и поясните графические символы, применяемые для записи алгоритмов.

11. Что такое блок-схема алгоритма?

12. Сформулируйте понятие алгоритмического языка.

Источник