Структурная схема циклического алгоритма

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

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

Программирование циклического процесса нагляднее всего пояснить на простом примере. Пусть требуется вычислить сумму членов ряда:

S = 1 + 1/2 + 1/3 + 1/4 + ... + 1/9 = Структурная схема циклического алгоритма - student2.ru

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

Проследим путь составления схемы алгоритма. Сначала рассмотрим способ вычисления любого члена ряда – без накопления их суммы.

Для вычисления первого члена ряда по формуле общего члена необходимы два блока, как показано на рис.1а.

Параметру цикла k присваивается начальное значение, равное единице. Подставляя это значение в формулу общего члена ряда, вычисляем значение первого члена, занося его в ячейку s.

Структурная схема циклического алгоритма - student2.ru

Для вычисления второго члена ряда параметр цикла необходимо увеличить на единицу, что выполняется оператором присваивания k = k+1 (новое значение параметра цикла равно предыдущему, увеличенному на единицу). Новое значение сохраняется в ячейке хранения значения параметра цикла, стирая при этом его прежнее значение. Теперь следует повторно выполнить оператор s=1/k, и алгоритм принимает вид, изображенный на рис.1б.

Действуя по схеме 1б, машина будет последовательно повторять выполнение блоков тела цикла бесконечное число раз, увеличивая параметр цикла при каждом повторении. Однако наш вычислительный процесс не бесконечен и должен прекратиться, как только параметр цикла станет больше девяти. Для этого следует добавить в схему алгоритма логический блок с проверкой условия k<=9. При истинности этого отношения нужно продолжать выполнение цикла, в противном случае- закончить цикл. Схема алгоритма приобретает вид, показанный на рис 1в.

Итак, мы научились вычислять любой член ряда по формуле общего члена. Но наша конечная цель – получить сумму этих членов. Выполнение записанных выше операторов не приводит к желаемому результату. Дело в том, что s – это простая переменная, чля хранения численного значения которой машина отводит одну ячейку памяти, в которой хранится единственное число. Поэтому запись в нее значения каждого следующего члена ряда приводит к утере значения предыдущего члена. Поэтому после выполнения данного алгоритма величина s будет равна значению последнего члена ряда.

Для обеспечения постепенного накопления суммы членов ряда необходимо оператор s = 1/k заменить на оператор s = s + 1/k (рис.1г). Однако при k=1 такой оператор нельзя вычислить, поскольку в его правой части находится переменная s, которая еще ни разу не вычислялась, и, следовательно, ее значение не определено. Поэтому до начала вычислений мы обязаны присвоить этой переменной начальное значение. Достаточно очевидно, что следует положить s = 0, т.к. только в этом случае получим истинное значение первого члена ряда при k = 1:

s = 0 + 1/k = 0 + 1/1 = 1.

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

Для записи циклических алгоритмов в языке СИ существует три различных оператора цикла. Каждый их них более удобен в определенной ситуации, хотя, в принципе, они практически взаимозаменяемы.

Оператор цикла for

Применение цикла for представляется более предпочтительным в случае, когда исходно известно начальное значение и закон изменения параметра цикла:

for(выражение_1; выражение_2; выражение_3)

{

тело цикла

}

В этой записи:

выражение_1 - задает начальное значение

параметра цикла;

выражение_2 - условие продолжения цикла;

выражение_3 - действие, выполняемое после каждого

выполнения тела цикла перед очередной

проверкой условия продолжения.

Используя этот оператор, наш алгоритм суммирования членов ряда может быть записан на языке СИ очень просто:

double s = 0.0;

int k;

for(k = 1; k <= 9; k++) s = s + 1.0/k;

Обратите особое внимание на вещественную единицу в числителе дроби. Если записать последний оператор как s = s + 1/k, то расчет будет неверен, поскольку деление будет производиться согласно арифметике целых чисел – результат деления тоже будет целым числом. Поскольку числитель дроби 1/kдля всех членов ряда, кроме первого, меньше знаменателя, то для них результат деления дает нуль. Поэтому итоговое значение величины s будет равно значению только первого члена ряда, т.е. единице.

По этой же причине тип переменной s выбран не int, а double – чтобы не терять десятичные знаки.

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

for(;;) { тело цикла }

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

int k = 10;

..........

for(;;)

{

.........

k--;

if(k) break;

}

Если опущено выражение_2, то считается, что оно истинно. В этом случае также получается бесконечный цикл.

Работа оператора for(...) описывается такой последовательностью шагов:

1. Вычисляется выражение_1 (если оно присутствует).

2. Вычисляется выражение_2 (если оно присутствует).

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

3. Выполняется тело цикла.

4. Вычисляется выражение_3 (если оно присутствует).

5. Переход к п.2.

Любое выражение, записываемое в заголовке цикла, может быть

довольно сложным и даже представлять собой последовательность нескольких выражений, соединенных операцией "запятая":

for(i=0; i<10; printf("\n %d",i), i+=2);

¦

¦ операция "запятая"

---------------------

Приведенный фрагмент цикла обеспечивает вывод на экран чисел 0, 2, 4, 6, 8 "столбиком".

Цикл for(...) всегда можно заменить эквивалентной записью

цикла while(...):

выражение_1;

while(выражение_2)

{

тело цикла;

выражение_3;

}

Однако, на наш взгляд, запись цикла for() более наглядна, поскольку все выражения, определяющие работу цикла, пишутся рядом в одном заголовке.

Предупреждение. Параметр цикла нельзя

Наши рекомендации