Циклические алгоритмы.

Арифметические циклические процессы.

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

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

Переменные, изменяющиеся в цикле - переменными цикла.

Алгоритм циклической структуры содержит следующие блоки:

1. Подготовка цикла: задание начальных значений переменных цикла перед его выполнением.

2. Тело цикла: действия, повторяемые в цикле для разных значений переменных цикла.

3. Модификации значений переменных цикла перед каждым новым его повторением.

4. Управление циклом: проверка условия продолжения цикла, если выполняется условие продолжения.

Применение циклов приводит к уменьшению длины алгоритма и сокращению времени на его составление.

Циклы бывают арифметические и структурные (структурные циклы связаны гуляниями нескольких переменных).

Арифметические циклы связаны, в основном, с изменением одной переменной. Они делятся на два типа:

ü циклы на достижение заданной точности, (итерационные);

ü циклы с известным числом повторений.

1. Циклический процесс называется итерационным, если заранее неизвестно количество повторений цикла, а конец вычисления определяется при достижении некоторой величены заранее заданной точностью вычисления.

Примеры итерационных циклов:

ü погрешность с заданной точностью;

ü заработная плата, пока не кончится весь массив.

Структуры итерационных процессов принято разделять на:

ü циклы с постусловием;

ü циклы с предусловием.

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

Рис. 1 Циклический процесс с предусловием

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

Для циклического процесса с постусловием характерна следующая схема рис.2:

Рис. 2 Циклический процесс с постусловием

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

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

Пример 1. цикл с “предусловием”

Пример 2. цикл с “постусловием”

2. Второй тип арифметических циклов – это цикл с известным числом повторении.

Этот цикл еще называют цикл со счетчиком. Число повторений тела цикла подсчитывается с помощью специальной переменной, для которой известны начальное и конечное значения, и шаг ее изменения.

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

I – параметр цикла; N и K – задают соответствующие начальное и конечное значение цикла.

На каждом шаге вычислений происходит последовательное приближение к искомому результату и проверка условия достижения последнего.

Пример 1. Составить алгоритм вычисления бесконечной суммы

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

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

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

Решая эту задачу "в лоб" путем вычисления на каждом i -ом шаге частичной суммы S:=S + ((-1)**(i-1)) * (x**i) / i

мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой р, то у следующего слагаемого числитель будет равен —р*х (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое m будет равно p/i, где i — номер слагаемого.

Пример 2. Вычислить сумму элементов заданной матрицы А(5,3).

S:= 0; нц для i от 1 до 5 нц для j от 1 до 3 S:=S+A[i,j] кц кц

Пример 3. Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.

i:=2; P:=1 нц пока i <= 10 j:=2 нц пока j <= 10 P:=P*A[i,j] j:=j+2 кц i:=i+2

Кц

Дата добавления: 2015-07-08