Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1339


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

 

Циклические   алгоритмы   являются   наиболее   распространенным видом алгоритмов, в них предусматривается повторное выполнение определенного набора действий в зависимости от некоторого условия, называемого условием окончания повторений. Такое повторное выполнение называют циклом. Повторяющиеся действия в цикле называются «телом цикла».

Существуют   два      основных       вида    циклических  алгоритмов:

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

Цикл с предусловием (цикл ПОКА) начинается с проверки условия выхода      из      цикла.      Это      логическое      выражение,      например I  <=  6  (эквивалентно  математическому  выражению  I  ≤  6).  Пока  оно истинно, то выполняются  действия цикла, которые должны повторяться. Если при изменении переменной I логическое выражение I <= 6 станет ложным, то есть I станет больше 6, то цикл с предусловием прекратит свои действия.

Цикл с постусловием (цикл ДО ТЕХ ПОР) функционирует иначе. Сначала выполняются один раз те действия, которые    подлежат повторению, затем проверяется логическое выражение, определяющее условие выхода из цикла, например, I > 6. Цикл повторяет действия, указанные в теле цикла, до тех пор, пока   условие выхода не станет истинным, в противном случае происходит повторение действий, ука- занных в цикле. Разновидности циклов приведены на рис. 10, а, б.

 

i = 1

i = 1

 

 

K:= K+1

а          б

i <= 6

 

+          K

i:= i+0,1

 

+

i > 6     K

 

K:= K+S

 

i:= i+1

 

 

Рис. 10. Виды циклических алгоритмов

а) цикл с постусловием;  б) цикл с предусловием

Классическим примером циклического алгоритма служит алгоритм для   вычисления   степени   числа   Y=Xⁿ.   Этот   алгоритм   может   быть реализован на основе операции умножения. Табличное представление такого  алгоритма,  отражающего  зависимость  Y  от  Х  при  изменении

показателя степени n от 1 до 3, представлено в табл. 2. В этой таблице показаны также рекуррентные соотношения между Y и Х, определяющие, как на каждом шаге зависит значение Y от значения Х и от  значения Y, вычисленного на предыдущем шаге.

 

Рекуррентные соотношения при вычислении Y=Xⁿ

Таблица 2

 

 

 

n

 

Y

Рекуррентные соотношения

1

Y[1]=X

Y=X

2

Y[2]=X*X или Y[2]=Y[1]*X

Y=X*X или Y=Y*X

3

Y[3]=X*X*X или Y[3]=Y[2]*X

Y=X*X*X или Y=Y*X

 

Пример 5. Требуется составить алгоритм получения на отрезке  Х € [-15,15] последовательности значений функции Y = SIN(X) в виде таблицы значений (X,Y) при изменении аргумента Х по формуле  X[k] = X[k-1] + h, где h = 1,5.

Решение. Такие задачи относят к задачам табулирования функций. Из условия задачи определяем, что начальное значение отрезка табулирования  X = –15, конечное значение – X = 15. Процесс получения множества пар (Х, Y) является итерационным, значит проектируемый алгоритм будет циклическим. Условие выхода из цикла Х > 15.

На рис. 12 представлен циклический алгоритм с предусловием вычисления табличного значения функции Y = SIN(X) на отрезке -15 < X < 15 при изменении Х на каждом шаге итерации на величину 1,5. Результатом выполнения алгоритма является циклический вывод множеств пар (Y, X).

 

Текстовая форма алгоритма

 

НАЧАЛО Присвоить Х = –15

Пока   Х <= 15 повторять

 

 

НАЧАЛО

 

X:= –15

 

X <=15

 

 

1. Вычислить Y = SIN(X)

 

2. Вывести     Y,X

 

3. Вычислить X = X+1,5

 

КОНЕЦ

+

 

Y = SIN(X) Y, X

X: = X+1,5

 

КОНЕЦ

 

 

Рис. 12. Циклический алгоритм табулирования функции Y = SIN(X)

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

S=x+x2+x3+…+xn.

Решение. Исходные данные для алгоритма – это переменные x и n. На каждом шаге будем вычислять очередной член суммы Y и прибавлять его к предыдущему значению суммы S. Для этого используем рекуррентную формулу вычисления степени Х (см. таблицу 3) Y=Y*Х, тогда сумма ряда на каждом шаге итерации будет вычисляться по формуле S=S+Y. Количество итераций K изменяется от 1 до n и равно количеству членов ряда. Начальное  значение суммы ряда S равно 0.

На рис. 13 представлен циклический алгоритм с предусловием для вычисления заданной суммы ряда.

 

НАЧАЛО

 

Ввод X, N

 

S:=0

 

Y:=Х

 

K:=1

 

+          K < N

 

K:=K+1

 

Y:=Y*Х

 

 

Вывод S

 

S:=S+Y

 

КОНЕЦ

 

Рис. 13. Алгоритм вычисления суммы ряда S=x+x2+x3+…+xn

Задания для самостоятельного выполнения

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

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

 

1. Вычислить число в факториале Y = X! (факториал Х).

2. Вычислить сумму ряда, общий член которого задан формулой

An = (x*n)/n!

3. При табулировании функции y = cos(x + a) на отрезке  [1, 10] c шагом

h=1 определить сумму значений y, больших p.

4. Подсчитать количество цифр в целом числе Х.

5. Вычислить сумму значений функции у = x2 на отрезке [1, 5] c шагом 1.