Структура цикл–пока. Обработка последовательностей

Цель:

· получить представление о типах последовательностей и их свойствах;

· получить представление о циклических процессах и методах их описания с помощью структуры ЦИКЛ–ПОКА;

· научиться использовать электронные таблицы для обработки рекуррентных выражений и определения суммы элементов убывающей последовательности с помощью структуры ЦИКЛ–ПОКА.

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

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

· Циклы, в которых количество повторений определяется некоторым условием.

· Циклы, в которых число повторений задается и оно конечно.

Циклические вычислительные процессы используются для обработки последовательностей.

Определение 1. В математике называется последовательностью и обозначается S={U_i} отображение, ставящее в соответствие целому значению i>0 некоторое значение, обозначаемое U_i.

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

Для приведенного выше определения предполагается существование формулы, с помощью которой можно вычислить любой элемент последовательности. Например, формула U_i = 2*i+1 задает значения:

   U₀ = 2*0+1 = 1 при i=0;

   U₁ = 2*1+1 = 3 при i=1;

   U₂ = 5 при i=2 и т.д.

Легко видеть, что при расчете элементов этой последовательности в формуле меняется только переменная i с шагом 1, которая указывает на элемент последовательности. 

В рекуррентных последовательностях значение U_i выводится из значения U_i-1, например, U_i = 2*U_i-1 + 1. Такие формулы иначе называются рекуррентными или итерационными. Примем, что начальное значение U₀ = 0. При различных i получаем значения:

   U₁ = 2*U₀ + 1 =1;

   U₂ = 2*U₁ + 1 =3;

   U₃ = 2*U₂ + 1 =7 и т.д.

Отметим, что в цикле, в котором вычисляется U_i, нужно также иметь значение U_i-1. Таким образом, необходимы две переменные: одна – для U_i-1, обозначаемая U1, а другая – для U_i, обозначаемая U2 и получаемая из U1 при помощи инструкции U2 = 2*U1+1.  На следующем шаге эти вычисления надо выполнить снова, но за U1 надо брать U2, вычисленное на предыдущем шаге. Поэтому в цикле необходима такая инструкция: U1 = U2. Это важный момент при обработке рекуррентных последовательностей, так как в противном случае рассчитанное значение переменной U2 не будет меняться, поскольку не меняется U1.

Определение 2. Последовательность S={u_i, i=1,2,3...} называется сходящейся к U^*, если lim |U_i - U^*|=0 при i. .

В практических расчетах анализируется неравенство |U_i - U_i-1| < eps, где eps – малое число, если неравенство выполняется, принимают U_i = U^*.

Определение 3. Последовательность S={u_i, i=1,2,3...} является убывающей, если lim |U_i|=0 при i     .

На практике обработку ее прекращают, если выполняется неравенство |U_i| < eps.

Определение 4. Последовательность S={u_i, i=1,2,3...} называется возрастающей, если lim |U_i|=  при i .  

На практике обработку ее прекращают, при выполнении условия |U_i| > C, где С – большое число.

Из этих примеров следует, что при обработке последовательностей по рекуррентным выражениям необходимо некоторое количество команд повторять, и число повторений при расчете задать заранее нельзя, так как оно будет определяться некоторым условием. Для описания алгоритмов обработки последовательностей используется управляющая структура ЦИКЛ–ПОКА, которая на псевдокоде имеет вид:

ПОКА Р?       

      A                                                                                          (1)

ВСЕ-ЦИКЛ,         

где Р – проверяемое условие; А – блок повторяемых инструкций. Согласно этой структуре, если логическое выражение является истиной, то начинается выполнение цикла, то есть выполняются команды, следующие за фразой ПОКА до тех пор, пока не будет встречена инструкция ВСЕ–ЦИКЛ. После этого выполнение цикла повторяется, то есть по достижению ВСЕ–ЦИКЛ управление будет передано на оператор, описывающий инструкцию ПОКА. Работа цикла будет завершена тогда, когда результат вычисления логического выражения P станет равным ЛОЖЬ. В этом случае управление передается команде следующей за ВСЕ–ЦИКЛ.

Если результат вычисления логического выражения Р равен ЛОЖЬ в первом проходе, то ни одна команда тела цикла не выполняется. Циклы ПОКА могут быть вложены друг в друга. При написании алгоритмов, содержащих ЦИКЛ – ПОКА, тело цикла должно быть сдвинуто вправо на три позиции относительно операторных скобок ПОКА и ВСЕ–ЦИКЛ.

Рассмотрим теперь, каким образом структура ЦИКЛ–ПОКА используется для решения чисто математических задач. Для построения соответствующей программной схемы исследуем структуру ЦИКЛ–ПОКА.

Прежде всего заметим, что цикл может закончиться только в том случае, если инструкция А так влияет на выражение Р, что через конечное число повторений значение Р станет ложным. Следовательно, в А должна быть по крайней мере одна переменная, которая встречается и в Р. Обозначим множество таких переменных через V. Тогда инструкция (1) может быть записана в виде программной схемы:

V=V0

ПОКА P(V)

    A(V)                                                                                                (2)

    V= f(V)

ВСЕ–ЦИКЛ

Здесь P(V) означает логическое выражение (условие), а V=f(V) – рекуррентное выражение для изменения общего параметра. Запись (2) называется схемой потому, что интерпретируя P(V), V, A(V) для конкретной задачи, можно получить различные программы, имеющие одинаковую структуру и характер выполнения.

Если обозначить через Vi значения переменной V после i-го этапа выполнения, то последовательность V1,V2,.., Vn будет обладать следующими свойствами:

V1=f(Vi-1)            для всех i > 0

Vi=Vj                    для все i=j

P(Vn)=ЛОЖЬ()

P(Vi)=ИСТИНА() для всех i < n

Заметим, что для V должно быть точно определено начальное значение V₀. Нарушение этого правила является наиболее распространенной ошибкой в программировании. Итерации заканчиваются, если существует такое n, при котором выполняется условие P(Vn)=ЛОЖЬ().

Пример 1. Пусть требуется решить задачу: найти минимальное n, при котором n! становится больше заданного значения С.

Легко видеть, что факториал F(n)=n!=1*2*3*…*n, n > 0 можно вычислить на основе следующих рекуррентных выражений

F(0)=1

F(i)= F(i-1)* i

i= i+1

Введем переменные f и i, значения которых после выполнения i-q итерации равны соответственно F(i) и i.

Задачу будем решать с помощью полученной выше программной схемы. Для этого определим компоненты P(V), V, A(V), f(V) с учетом введенных выше обозначений. Очевидно, что V0 – это f=1 и i=1, P(V) – f < C, A(V) – f=f*I, V=f(V) – i=i+1.

Проект программы, который получается после подстановки конкретных выражений для компонент в схему (2), имеет вид

ВВОД С

f=1: i=1

ПОКА f < C

i=i+1: f=f*i

ВСЕ -ЦИКЛ

ВЫВОД “Значение для n=”: i

Так как i растет, принимая значения из последовательности натуральных чисел, и так как С > 0, то решение будет получено.

Пример 2. Вычислить y= , используя итерационную формулу Ньютона:

y_i = y_i-1+(x/ y_i-1 – y_i-1)/2.

Вычисления закончить, когда модуль разности y_i – y_i-1 <= eps. Здесь eps малая величина, например, 0,001. Для отладки принять х=3,61 и y₀=1.

Введем две переменные Y1, где будет храниться y_i, и Y0, которая будет соответствовать y_i-1. После определения всех компонент программной схемы проект программы, решающий поставленную задачу, будет иметь вид

ВВОД X, Y0< EPS

Y1=Y0+(X/Y0 – Y0)/2

ПОКА ABS(Y1-Y0) > EPS

    Y0=Y1

     Y1= Y0+(X/ Y0 – Y0)/2

ВСЕ-ЦИКЛ

ВЫВОД “Корень квадратный из ”: X: “=”: Y1