1.2.2. Общие вопросы организации циклов

Выше были рассмотрены примеры циклических алгоритмов, которые часто встречаются в практике. Прежде чем перейти к особенностям орга-низации циклических процессов, рассмотрим ещё один типичный пример.

Пример 1.9. Пусть СП вычисления EXP в нашем распоряжении нет, и нам самим требуется составить соответствующий алгоритм. Запишем разложение exp(-x) в ряд Тейлора, ограничившись n-м членом:

(1.15)

Обозначим h_i общий член ряда:

(1.16)

Тогда ряд (1.15) может быть представлен выражением

(1.17)

Вычисления h_i можно проводить двояко:

 непосредственно по (1.16);

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

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

. (1.18)

Ясно, что второй способ более рациональный.

При вычислении суммы ряда (1.17) также более рационально использовать предыдущие результаты:

, (1.19)

где S_i - значение частичной суммы членов ряда с 1-го по i-й включительно.

Нетрудно видеть, что при определении значения y=exp(-x) для конкретного значения x=x₀ достаточно организовать один цикл, в котором объединить вычисления значений h_i и S_i.

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

y_n = , (1.20)

где q_i - коэффициенты разложения функции в ряд.

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

• n задано или известно в результате анализа погрешности ряда (константа n – исходное данное). Чаще всего это бывает, если опреде-ляется значение функции для одного конкретного значения x=x₀ или небольшого числа мало отличающихся (в том смысле, что для них n не изменяется) значений x. Тогда организуются циклические вычисления, которые заканчиваются при достижении параметром i цикла значения n;

• n заранее неизвестно, однако задана допустимая погрешность , и циклический процесс заканчивается по условию выполнения неравенства

y_n+1-y_n  , (1.21)

или

R_n(x)  , (1.22)

где R_n(x) - остаточный член ряда (константа R_n вычисляется заранее).

В примере 1.9 ряд является знакопеременным, поэтому [4] погрешность ряда не превышает значения первого отброшенного его члена, равного

R_n(x) (1.23)

Вычислительный процесс организуется по-разному в случае вычис-ления у=f(x) для конкретного значения x=x₀ и для некоторого множества значений x_i (например, необходимо построить график у=f(x), ахв). В пер-вом случае вычисление выполняется однократно и потому нет необходи-мости в дополнительной организации вычислительного процесса; во втором случае необходимо организовать циклический перебор всех значений x_i, используя номера i-x точек на оси ОХ при неравномерном разбиении отрезка [a, b] либо приращение по х,

(1.24)

при равномерном разбиении на к интервалов (к - известно), и тогда

x_i = a + i*x. (1.25)

Отметим, что полином Q_n(x) может быть записан аналогично (1.20). Однако ряд и полином существенно отличаются: ряд имеет общий член, так как коэффициенты ряда вычисляются по определённому закону, а у полинома коэффициенты могут быть произвольными, поэтому у него может отсутствовать общий член. Вопрос определения n для полинома должен решаться отдельно в каждом конкретном случае.

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

Стандартные способы построения циклов в программировании – использование конструкций for, while <условие> do <оператор>, repeat <оператор> until <условие> (рис. 1.15).

Оператор for имеет внутренний счётчик в обоих вариантах реали-зации (I_нач, I_кон - целые константы):

for I:= I_нач to I_кон do <оператор> - счёт в прямом направлении;

for I:= I_кон downto I_нач do <оператор> - счёт в обратном направлении.

Здесь изменение параметра цикла происходит на 1 по умолчанию; в некоторых языках программирования используется явное указание на шаг (step) приращения I.

Применять оператор for целесообразно при известном числе повторений в цикле.

На рис. 1.15,а и б приведены фрагменты СА для оператора for; здесь S1, S2 - тело цикла.

Запишем фрагмент программы примера 1.6 (строки 3-9) с использо-ванием оператора for (здесь invel(lel, rel) - процедура инверсии элементов):

с:=А[1];

for i:=1 to n-1 do

begin

lel:=c; rel:=A[i+1];

if lel<rel then invel(lel,rel);

c:=rel

end;

minel:=c;

Этот же фрагмент можно упростить, исключив процедуру invelи соответственно переменныеlel и rel (на каждом шаге запоминается мини-мальное значениеспары элементов):

c:=A[1];

for i:=2 to n do

begin

if ca[i] then c:=a[i]; (*текущий минимальный элемент*)

end;

minel:=c;

Реализация операторов while...do и repeat...until в виде СА приведена на рис. 1.15,в и г. Смысл этих операторов заключается в следующем: для первого - пока выполняется условие W, делать S1, S2,..., а для второго - повторять S1, S2,..., пока не выполнится условие U. Раз-личие этих условных операторов заключается в том, что при организации одного и того же вычислительного процесса (S1; S2;..., Sn) условия W и U должны быть противоположны, U=; кроме того, во втором случае после-

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

Эти операторы можно использовать и при известном числе повторе-ний; при этом в теле цикла должен быть предусмотрен счётчик, а усло-вием выхода из цикла будет его конечное значение.

Операторы while...do и repeat...until так же, как и оператор if, соз-дают простое разветвление, но в отличие от операторов if они предназ-начены для многократного выполнения одного и того же вычислительного процесса (S1;S2;...Sn).

Отметим, что организация цикла на рис. 1.11 соответствует опера-тору repeat..until для первого варианта СА и оператору while..do - для второго (в обоих вариантах со встроенным счётчиком).

Под термином организация цикла понимается правильное выпол-нение начала цикла, его завершения и собственно тела цикла.

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

При продумывании реализации тела цикла необходимо понять, ка-кие операторы не зависят от параметра цикла, и вынести их из цикла либо обозначить простой переменной, что сократит время выполнения алго-ритма. Если переменная X[I], зависящая от параметра цикла I, встре-чается в теле цикла более двух раз, то имеет смысл переобозначить её (например, Y:=X[I]), с тем чтобы не тратить время (кроме первого раза!) на вычисление адреса этой переменной в оперативной памяти; при выходе из итерации (цикла) следует вернуться к старому обозначению. Важно обнаружить и использовать рекуррентные связи между переменными.

При организации завершения цикла необходимо решить вопрос о том, каким должен быть выход из цикла (когда и как: с использованием предусловия или постусловия)? При этом должно быть гарантировано, что для встроенного счётчика все итерации имеют место. Установить, что выход из цикла осуществляется с нужными значениями параметра цикла. Разобраться, с какими значениями переменных циклический алгоритм заканчивает работу, точнее, надо так организовать цикл, чтобы это были нужные для следующего фрагмента СА значения.

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

Ошибки в организации цикла связаны обычно с неправильным выполнением начала цикла или его конца; именно этим моментам и следует уделить особое внимание.

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