Способы построения циклических вычислительных процессов

Содержание: 

1. Способы построения  циклических вычислительных  процессов в программах.

2. В компьютер вводится  N вещественных чисел. Составить программу, выдающую на экран среднее арифметическое значение этого набора. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

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

подготовка (инициализация) цикла (И);

выполнение вычислений цикла (тело цикла) (Т);

модификация параметров (М);

проверка  условия окончания цикла (У).

Порядок выполнения этих этапов, например, Т  и М, может изменяться. В зависимости  от расположения проверки условия окончания  цикла различают циклы с нижним и верхним окончаниями. Для цикла с нижним окончанием тело цикла выполняется как минимум один раз, так как сначала производятся вычисления, а затем проверяется условие выхода из цикла.

 
 
 
 
 

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

Цикл  называется детерминированным, если число  повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла  заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

Тело  цикла - это многократно повторяющийся участок программы.

Параметр  цикла - это переменная, которая принимает новые значения при каждом повторении цикла (циклы бывают простые и сложные).

Общий вид цикла n раз

            В общем виде цикл n раз записывается  так:

  нц  число повторений раз  

| тело  цикла (последовательность команд)     

 кц

            Служебное слово нц (начало цикла)  и кц (конец цикла) пишутся строго  одно под другим и соединяются вертикальной чертой. Правее этой черты записывается повторяемая последовательность команд (тело цикла).

            Число повторений – произвольное  целое число.

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

Общий вид цикла пока

            В общем виде цикл пока записывается  так:

            нц пока условие

            | тело цикла (последовательность  команд)

            кц

            При выполнении цикла компьютер повторяет следующие действия:

            а) проверяет записанное после  служебного слова пока условие;

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

Общий вид цикла для

            нц для i от i1 до i2

            | тело цикла (последовательность  команд)

            кц

            Здесь i – имя величины целого типа, i1, i2 – произвольные целые числа или выражения с целыми значениями. Тело цикла последовательно выполняется для i = i1, i = i1 + 1, i1 + 2, …i = i2.

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

Цикл n раз и цикл пока

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

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

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

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

 
 
 
 
 
 
 
 
 

  
 
 

Рис.1. Типовая  структура управляющей программы с бесконечным циклом.

МЦП имеют  разнообразную структуру, сложность  которой необходимо оценивать по специальным критериям. В.В.Липаевым предложен удобный и объективный  критерий сложности программных  модулей, а именно: число и суммарная  длина путей в управляющем графе модуля [1]. При этом учитываются только условные операторы и операторы выбора. Однако этого критерия явно недостаточно для МЦП со статической памятью, ибо при анализе МЦП необходимо помнить значения всех статических переменных, установленные в предшествующем цикле. Помимо этого, никаких рекомендаций по стандартизации алгоритмов и программ, кроме давно известного структурного программирования [2] на общеупотребительных языках программирования типа Си и Паскаль - нет. В данной статье предлагается восполнить эти пробелы применительно к МЦП.  

2. Фрагменты модулей  циклических программ 

Двухполюсным  фрагментом, или просто фрагментом, будем считать участок программы  с одним входом и одним выходом (включая операторы циклов) в предположении, что рассматриваемые МЦП структурированы. Простейший фрагмент включает единственный оператор. Последовательность фрагментов также является фрагментом. МЦП в свою очередь является фрагментом и состоит из последовательности фрагментов.

В [3] предложен  метод независимых фрагментов для синтеза структуры модулей, реализующих таблицы решений. При этом независимым считается такой фрагмент, который можно вставить в любом месте последовательности фрагментов модуля. Независимость местоположения такого фрагмента обусловлена тем, что анализируемые в нем данные не формируются в указанной последовательности фрагментов, а формируемые в независимом фрагменте данные не анализируются в данной последовательности фрагментов. Поэтому независимые фрагменты могут выполняться параллельно (псевдопараллельно). На рис. 2 показаны возможные варианты реализации модуля с двумя независимыми фрагментами. В вариантах “а” и “б” фрагменты переставлены местами без искажения существа программы; в варианте “в” фрагменты реализуются параллельно.

  
 
 
 
 
 
 
 
 
 
 

Рис.2. Варианты реализации модуля с независимыми фрагментами:

а) и  б) - последовательная реализация,

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

Зависимым фрагментом является такой, местоположение которого зависит от местоположения другого (других) фрагмента  в модуле. Будем различать сверху- и снизу зависимые фрагменты. Сверху-зависимый фрагмент должен быть расположен всегда ниже некоторого фрагмента, в котором формируются переменные, используемые в данном (зависимом) фрагменте. Снизу-зависимый фрагмент должен размещаться всегда выше фрагмента, в котором используются переменные, формируемые в данном фрагменте. Два зависимых фрагмента, один из которых является сверху зависимым от второго, а второй снизу зависимым от первого, будем называть взаимно зависимыми фрагментами. Их нельзя менять местами и нельзя реализовывать параллельно. На рис. 3 приведен пример модуля с взаимно зависимыми фрагментами. Между взаимно зависимыми фрагментами могут находиться другие, зависимые или не зависимые от них. Рис.3. Модуль с зависимыми фрагментами.

Фиксированным будем называть зависимый фрагмент, местоположение которого в модуле строго определено. Например, в модуле распознавания символа, введенного с клавиатуры, первым должен быть снизу зависимый фрагмент непосредственно ввода символа. Операторы “начало” и “конец” модуля есть фиксированные фрагменты.

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

Так как  модули программы являются ее фрагментами, то все перечисленные определения  распространяются и на них; модули могут  быть зависимыми, фиксированными и  независимыми.

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

3. Число маршрутов  в модулях циклических  программ 

Рассмотрим  влияние зависимости фрагментов на критерий сложности модулей по Липаеву, то есть на число маршрутов в модулях. В дальнейшем под термином “маршрут” (“путь”) будем подразумевать так называемые условные (объясняется ниже) маршруты (пути).

Обозначим S - общее число маршрутов (путей) в модуле, а Sn - число путей в n-ом фрагменте этого модуля.

Пусть модуль содержит только зависимые фрагменты (рис. 3). Управляющий граф [1] этого  модуля изображен на рис. 4,а, из которого следует, что фрагмент 1 содержит 5 маршрутов, а фрагмент 2 - 3 маршрута. Так как  каждый маршрут фрагмента 2 зависит от маршрутов фрагмента 1, то общее число маршрутов в данном модуле равно произведению чисел маршрутов каждого из фрагментов, то есть S = S1 * S2.

  
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис.4. Расчетные  маршрутные схемы (РМС):