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

Структурограммы (диаграммы нэсси-шнейдермана)

 

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

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

ДДДДДДДДДДДДДДДД   - блок обработки (вычислений); любой прямоугольник внутри структурограммы есть также блок обработки

 

ДДДДДДДДДДДДДДДД    - блок следования: последовательность блоков обработки

 

ДДДДДДДДДДДДДДДД - блок решения; обозначает структуру ветвления

 

ДДДДДДДДДДДДДДДДД - блок варианта; является расширением блока решения.

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

 

ДДДДДДДДДДДДДДДДД - если все условия известны, правую часть блока варианта оставляют незаполненной или опускают совсем

 

ДДДДДДДДДДДДДДДДД - блок цикла с предусловием и блок цикла с параметром

 

ДДДДДДДДДДДДДДДДД - блок цикла с постусловием; внизу располагается условие окончания цикла

 

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

 

Вложенные алгоритмические структуры

 

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

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

Пусть требуется написать алгоритм решения задачи табулирования функции 2-х переменных  z = x + y , в которой х меняется от 1 до 3 с шагом   х = 0.5, а y меняется от -1 до 1 с таким же шагом.

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

 

x = 1.0

y = -1.0            z = ... y = -0.5  z = ...

.           .   .

y =  1.0            z = ...

 

x = 1.5

y = -1.0            z = ...

.           .   .

x = 3.0

y = -1.0            z = ...

.           .   .

y =  1.0            z = ...

 

Если мы принимаем такую структуру вывода, то очевидно, что параметром внешнего цикла является х, а параметром вложенного - переменная y. Блок-схему такого алгоритма можно представить так:

 

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

3 - 1

n  =  -------  + 1 = 5.

0.5

Для самостоятельно выделенного внутреннего цикла по y имеем число повторений

1 - (-1)

n  =  ---------  + 1 = 5.

0.5

Из  полученных  расчетов  следует,  что  в  процессе  решения  данной  задачи  общее количество повторений тела внутреннего цикла, в том числе и вычислений по формуле для z, составит n = n  * n   = 5 * 5 = 25. Здесь вполне можно поменять местами внешний и вложенный циклы, от этого не изменятся ни структура алгоритма, ни требуемый для решения объем вычислений.

Изменим часть условия задачи, предположив, что шаг изменения переменной х остался тем же, а вот   y = 0.1 . Тогда число повторений цикла по y будет равно  n  =  (1 + 1)/0.1  + 1 = 21. Если этот цикл сделать внутренним, то в процессе решения задачи тело цикла по у повторится 5

* 21 = 105 раз. Тело внешнего цикла, в которое кроме тела цикла по у входят и другие действия, повторится  5  раз.  Таким  образом,  общий  объем  вычислений  в  алгоритме  можно охарактеризовать цифрой  n  * n  + n  = 105 + 5 = = 110. Поменяем теперь циклы по х и по у местами. Число повторов внутреннего цикла остается тем же - 105, а вот общий объем вычислений изменится, поскольку все операции внешнего цикла повторятся 21 раз, следовательно, общий объем вычислений в данном случае пропорционален  n  * n  + n  = 105 +

21 = 126 > 110.

Изменим   еще   раз   условие   задачи.   Пусть   переменные   х   и   у   изменяются   как   в первоначальном варианте, а вот сама функция z

- иная:

z = e  + x.

 

Казалось бы, объем вычислений не зависит от того, какой цикл является внешним, а какой - вложенным, и пропорционален n  * n  + n  = 25 + 5 = 30. Рассмотрим, однако, две структурограммы алгоритма для случая, когда цикл по у является внешним:

Если алгоритм решения реализуется по левой структурограмме, то, в принципе, нет разницы, по какому параметру организуется внешний цикл. Все равно вычисления по формуле для z, включая экспоненту, будут выполняться 25 раз. Согласно правому алгоритму, вычисление экспоненты вынесено во внешний цикл и поэтому выполняется только 5 раз. Задача будет решена быстрее, однако теперь переменные х и у неравнозначны.

Итак, можно сформулировать следующие правила организации вложенных циклов:

1) если условия задачи прямо не определяют, по какому параметру организуется внешний цикл, а по какому - внутренний, следует внешний цикл формировать по переменной, с которой связаны наиболее сложные вычисления;

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