Способы описания алгоритмов

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

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

Пример. Алгоритм нахождения наибольшего общего делителя двух натуральных чисел:

1. задать два числа;

2. если числа равны, то взять любое из них в качестве ответа, в противном случае – продолжить выполнение алгоритма;

3. определить большее из чисел;

4. заменить большее число разностью большего и меньшего чисел;

5. повторить алгоритм с шага 2.

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

Пример. Определить площадь треугольника по трем известным длинам сторон:

алг Площадь_треугольника (вещ А, В, С)

арг (А,В,С)

рез S

нач

Р=(А+В+С)

S= КОРЕНЬ(Р*(Р-А)*(Р-В)*(Р-С))

кон

В примере служебные (зарезервированные) слова написаны с подчеркиванием. В заголовке объявлены три вещественных параметра А, В, С, через которые передаются длины сторон треугольника. В теле программы используется функция нахождения квадратного корня КОРЕНЬ( ).

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

В схеме алгоритма каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, представленная в виде блочного символа (блока), называемого символом действия. Символы действия соединяются линиями переходов, определяющими очередность выполнения действий. Форма символов установлена ГОСТ 19.701-90 (ИСО 5807-85), а правила составления схем алгоритмов – ГОСТ 19.701-90 (ИСО 5807-85). Наиболее часто употребляемые символы действий приведены ниже в таблице.

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

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

Линии переходов используются для обозначения порядка выпол­нения действий. Для улучшения наглядности следует придерживать­ся стандартных правил изображения линий передач управления – сверху вниз и слева направо. Если необходимо показать передачу управления снизу вверх или справа налево, то направление следует отметить стрелкой.

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

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

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

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

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

При составлении схем алгоритмов соблюдают следующие правила:

1. каждый блок алгоритма имеет единственную точку входа, кроме блока пуска, который не имеет входа;

2. каждый безусловный блок имеет единственную точку выхода, кроме блока останова, который ее не имеет;

3. каждый условный блок имеет два или три выхода, которые можно пометить условиями: ДА, НЕТ или >0, =0 и <0;

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

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

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