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

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

Рассмотрим сущность базовых алгоритмических структур.

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

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

2. Ветвящаяся структура (ветвление, развилка). Часто   в зависимости от ситуации нам приходится выбирать ту или иную последовательность действий. Например,

утро

да

нужно

t >37

?

нет

придѐтся идти

вызвать врача

на занятия

завтрак

Рис.1.1. Блок-схема «бытового» алгоритма с ветвлением

a          b,

если

a, b - одного знака;

если

a, b - разных знаков.

начало

ввод a, b

c > 0

y = a + b

y = a2 + b2

вывод y

конец

Рис. 1.2. Блок-схема математического алгоритма с ветвлением

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

Встречаются случаи, когда одна из ветвей альтернативы не содержит никаких действий. Пример - вычисление функции y = tg x  для различных х:

ввод x

да        нет

x ≠0

y = a b/ x

вывод y

Рис.1.3. Блок-схема алгоритма с обходом

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

В языке Си рассмотренные структуры поддерживают следующие операторы:

- ветвление

if (условие) {блок 1}else {блок 2}

- обход

if (условие) {блок}.

Если блок содержит только один оператор, фигурные скобки можно опустить.

Примеры:

- для алгоритма рис. 1.3 оператор обхода  if (x != 0) {y = a  b/x; printf(“y = \%f ”,y);}

3. Циклическая структура.

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

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

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

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

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

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

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

i = n1; n2;        n

изменение параметра. В качестве примера рассмотрим задачу вычисления факториала x!

Правила организации цикла с параметром:

1) параметр цикла, его начальное и конечное значения желательны целого типа;

2) запрещается изменять i, n1, n2 в теле цикла;

3) запрещается попадать в цикл с параметром, минуя его заголовок;

4) при выходе из цикла значение параметра цикла не определено, поэтому использовать его для дальнейших вычислений не следует;

5) текущее значение параметра цикла сохраняется при досрочном выходе из цикла;

6)  цикл  с  параметром  может  не  выполниться  ни  разу;  это  происходит,  если  n1  >  n2  при инкремента параметра (++) в цикле, или если n1 < n2 при декременте параметра (--).

Последнее  правило  означает,  что  по  способу выполнения  цикл  с  параметром представляет собой вариант цикла с предусловием.

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

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

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

Отметим, что каждая из рассмотренных выше алгоритмических  структур имеет один вход и один выход.