Запись алгоритмов в виде блок-схем
Алгоритмы можно записывать по-разному. Форма записи, состав и количество операций алгоритма зависят от того, кто будет исполнителем этого алгоритма. Если задача решается с помощью ЭВМ, алгоритм решения задачи должен быть записан в понятной для машины форме, т. е. в виде программы. Всякий алгоритм может быть:
- записан на естественном языке;
- изображен в виде блок-схемы;
- записан на алгоритмическом языке;
Схема алгоритма – графическое представление алгоритма, дополняется элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой – блоком. Причем правило выполнения схем алгоритмов регламентирует ГОСТ 19.002–80 (единая система программной документации) см. табл. 5.
Блоки на схемах соединяются линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу–вверх и справа налево — стрелка обязательна. Количество входящих линий для блока не ограничено. Выходящих линий – одна, за исключением логического блока.
Таблица 5
Основные элементы блок-схем
|
№ п/п |
Символ |
Наименование |
Содержание |
Размеры по ГОСТ 19.003–80 (ЕСПД): а=10,15,20 мм b=1.5*а |
|
1. |
|
Блок вычислений |
Вычислительные действия или последовательность действий. |
|
|
2. |
|
Логический блок |
Выбор направления выполнения алгоритма в зависимости от некоторого условия. |
|
|
3. |
|
Блоки ввода-вывода данных |
1. Общие обозначения ввода (вывода) данных (вне зависимости от физического носителя) 2. Вывод данных, носителем которых является документ. |
|
|
4. |
|
Начало (конец) |
Начало или конец алгоритма, вход или выход в программу. |
|
|
5. |
|
Процесс пользователя (подпрограмма) |
Вычисление по стандартной программе или подпрограмме |
|
|
6. |
|
Блок модификации |
Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма. |
|
|
7. |
|
Соединитель
|
Указание связи прерванными линиями между потоками информации в пределах одного листа. |
|
|
8. |
|
Межстраничные соединения
|
Указание связи между информацией на разных листах. |
|
Базовые структуры алгоритмов - это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательных действий. К основным структурам относятся следующие - линейные (Рис. 5.а), разветвляющиеся (Рис. 5.б), циклические (Рис. 5.в).
Рис. 5. Базовые структуры алгоритмов и программ
Линейными называются алгоритмы, в которых действия осуществляются последовательно друг за другом. Стандартная блок-схема линейного алгоритма приводится на Рис. 6 а (вычисление суммы двух чисел - А и В).
Разветвляющимся называется алгоритм, в котором действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (серий).
В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, команда ветвления состоит из условия и двух последовательностей команд.
Примером может являться разветвляющийся алгоритм, изображенный в виде блок-схемы (Рис. 6.б). Аргументами этого алгоритма являются две переменные А, В, а результатом — переменная X. Если условие А >= В истинно, то выполняется операция Х:=А*В, в противном случае выполняется Х:=А+В. В результате печатается то значение переменной X, которое она получает в результате выполнения одной из серий команд.
Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла - последовательность команд) выполняются многократно. Однако слово “ многократно” не значит “до бесконечности”. Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности- получения результата за конечное число шагов.
Перед операцией цикла осуществляется операции начального присвоения значений тем переменным, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: блок проверки условия и блок, называемый телом цикла, Если тело цикла расположено после проверки условий P (цикл с предусловием), то может случится, что при определенных условиях блок тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл типа пока (здесь условие – это условие на продолжение цикла).
|
а). Линейный алгоритм |
б). Алгоритм с ветвлением |
в). Алгоритм с циклом |
Рис. 6. Примеры структур алгоритмов
Возможен другой случай, когда тело цикла выполняется по крайней один раз и будет повторятся до тех пор, пока не станет истинным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием, или цикла типа до. Истинность условия в этом случае- условие окончания цикла. Отметим, что возможна ситуация с постусловием и при организации цикла–пока. Итак, цикл–до завершается, когда условие становится истинным, а цикл–пока – когда становился ложным. Современные языки программирования имеют достаточный набор операторов, реализующих как цикл - пока, так и цикл – до.
Рассмотрим циклический алгоритм типа пока на примере алгоритма вычисления факториала, изображенного на Рис.6.в. Переменная N получает значение числа, факториал которого вычисляется. Переменной N!, которая в результате выполнения алгоритма должна получить значение факториала, присваивается первоначальное значение 1. Переменной К также присваивается значение 1. Цикл будет выполняться, пока справедливо условие N³K. Тело цикла состоит из двух операций N!= N!*K и К=К+1.
Циклические алгоритмы, в которых тело цикла выполняется заданное число раз, реализуются с помощью цикла со счетчиком. Цикл со счетчиком реализуется с помощью команды повторения.
Процесс решения сложной задачи довольно часто сводится к решению нескольких более простых подзадач. Соответственно при разработке сложного алгоритма он может разбиваться на отдельные алгоритмы, которые называются вспомогательными. Каждый такой вспомогательный алгоритм описывает решение какой-либо подзадачи.
Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в его систему команд) и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы подробно расписываются с использованием команд, понятных исполнителю.