Структурограммы (диаграммы нэсси-шнейдермана)
Изображение алгоритма с помощью структурограммы отвечает всем основным требованиям структурного программирования. Главное - запрещены произвольные передачи управления, а сама схема передачи изображается не с помощью линий как в блок-схемах, а с помощью вложенных структур. Каждый блок структурограммы имеет форму прямоугольника и может быть вписан в любой прямоугольник другого блока. Пояснительные записи внутри блоков выполняются на естественном языке или обычными математическими выражениями. Для изображения алгоритма используются следующие блоки: ДДДДДДДДДДДДДДДД - блок обработки (вычислений); любой прямоугольник внутри структурограммы есть также блок обработки
ДДДДДДДДДДДДДДДД - блок следования: последовательность блоков обработки
ДДДДДДДДДДДДДДДД - блок решения; обозначает структуру ветвления
ДДДДДДДДДДДДДДДДД - блок варианта; является расширением блока решения. Варианты, известные точно, размещаются слева. Остальные объединяют в один, называемый выходом по несоблюдению условий, и располагают справа
ДДДДДДДДДДДДДДДДД - если все условия известны, правую часть блока варианта оставляют незаполненной или опускают совсем
ДДДДДДДДДДДДДДДДД - блок цикла с предусловием и блок цикла с параметром
ДДДДДДДДДДДДДДДДД - блок цикла с постусловием; внизу располагается условие окончания цикла
В качестве примера приведем структурограмму алгоритма решения задачи табуляции функции, условия которой приводились выше.
Вложенные алгоритмические структуры
Если одна алгоритмическая структура является частью другой алгоритмической структуры, то она считается вложенной. Так, в предыдущем примере структура ветвление входит в цикл, а последняя является частью следования. Таким образом, можно говорить и об уровне вложенности. Наибольший интерес с точки зрения создания эффективного алгоритма представляет случай, когда в состав одного цикла входит другой цикл. Такая алгоритмическая структура обычно называется сложным циклом; цикл, охватывающий другой (другие) цикл, называется внешним, а цикл, входящий во внешний, - внутренним или вложенным. Существуют определенные правила организации таких структур, для знакомства с которыми вначале рассмотрим пример. Пусть требуется написать алгоритм решения задачи табулирования функции 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) при прочих равных условиях задача будет решаться быстрее, если внешний цикл имеет меньшее число повторений, чем отдельно взятый внутренний цикл.
|
|
