Базовые алгоритмические структуры

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

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

Рис. 10.3. Алгоритмическая структура «следование».

Ветвление (условие, развилка) описывает выполнение одного из двух вариантов действий в зависимости от выполнения или невыполнения некоторого условия. Каждый вариант образует отдельную ветвь алгоритма. После выполнения требуемых действий обе ветви сливаются в одной точке алгоритма (рис. 10.4). Если в одной из ветвей действия отсутствуют, то ветвление называют неполным.

На естественном языке полное ветвление выражается фразой «ЕСЛИ условие истинно, ТО выполняются действия 1, ИНАЧЕ выполняются действия 2». Неполное ветвление выражается как «ЕСЛИ условие истинно, ТО выполняются действия 1».

Рис. IO.4. Алгоритмическая структура «ветвление».

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

Цикл с предусловием (цикл-while. цикл-пока) описывает повторение действий, пока некоторое условие, проверяемое перед телом цикла, остается истинным (рис. 10.5). Количество повторений заранее неизвестно. Кроме тот, тело цикла вообще может быть не выполнено, если условие ложно с самого начала. На естественном языке цикл с предусловием выражается фразой «ПОКА условие истинно, выполнять тело цикла».

Рис. 10.5. Алгоритмическая структура «цикл с предусловием».

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

Введение

этих конструкций, в частности, сокращает время, затрачиваемое на запись алгоритма.

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

Рис. 10.6. Алгоритмическая структура «выбор».

Цикл с параметром (цикл-for, с известным числом повторений, счетный цикл) описывает повторение тела цикла указанное количество раз (рис. 10.7).

Рис. 10.7. Алгоритмическая структура «цикл с параметром».

В символе начала цикла указывается параметр (счетчик) цикла, а также начальное и конечное значения а и b соответственно. Необязательное значение h указывает на шаг изменения величины г при каждом новом повторении тела цикла. Перед первым выполнением тела цикла г := а, перед вторым — г := а 4- Н. перед третьим — г := а 4- 2h и т. д. При последнем выполнении г := 6.

Цикл с постусловием (цикл repeat-until, цикл-до) описывает повторение действий, пока некоторое условие, проверяемое после тела цикла, остается ложным. Блоксхема этого типа цикла приведена на рис. 10.8. Как и в случае цикла с предусловием, заранее неизвестно количество повторений тела цикла, но несложно видеть, что оно всегда выполнится как минимум один раз. На естественном языке цикл с постусловием выражается фразой «Выполнять действия, ДО ТЕХ ПОР, пока условие ложно».

Рис. 10.8. Алгоритмическая структура «цикл с постусловием».

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

Блок-схемы циклов с преди постусловием иногда записываются не в соответствии с ГОСТ 19.701 90, хотя и с использованием разрешенных этим стандартом блоков. На рис. 10.9, а приведена блок-схема цикла с предусловием, на рис. 10.9, б — с постусловием.

Все рассмотренные алгоритмические структуры имеют одну характерную особенность: наличие одного входа и одного выхода. Так как любой алгоритм может быть представлен как комбинация БАС, то любая программа с точки зрения логической oj>- ганизации имеет последовательную структуру. При этом структуры могут быть вложенными. Например, в теле цикла допускается наличие другого цикла. В этом случае говорят про внешний и внутренний (влоэюеиный) циклы по отношению друг к другу.

БАС и производные от них структуры легли в основу структурного программирования, основные принципы которого были сформулированы Э. Дейкстрой и дополнены.

Рис. 10.9. Альтернативная запись итерационных циклов.

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