Информатика - Учебное пособие

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

 

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

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

 

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

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

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

 

утро

 

 

 

 

я, кажется, заболел

 

 

измерим температуру

 

 

 

да

 

нужно

 

t >37

?

нет

 

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

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

на занятия

 

 

завтрак

 

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

 

 

 
2) вычислить выражение

a          b,

 

 

если

 

 

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

 

 
y          a 2       b 2 ,

 

если

 

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

 

начало

 

ввод a, b

 

 

 

c = 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.2 оператор ветвления   if (c > 0) y = a + b; else y = a2 + b2;

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

 

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

 

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

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

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

 

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

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

 

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

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

 

i = n1; n2;        n

 

 

 
Здесь i – параметр цикла, n1 – его начальное значение, n2 – конечное значение,        n –

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

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

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

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

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

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

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

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

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

 

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

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

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

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