Лекция 4.++Итерационные циклы и рекуррентные вычисления (Воробьева И.А. - Информатика. Язык Паскаль)

1Воробьева И.А. «Информатика. Язык Паскаль»4.5. Итерационные циклы и рекуррентные вычисленияИтерационный цикл – это цикл, в котором заранее не известночисло повторений тела цикла. Выход из итерационного циклаосуществляется при выполнении заданного условия.До сих пор мы рассматривали итерационные циклы, в которыхлибо знали реальное число шагов исполнения тела цикла (заменапараметрического цикла итерационным), либо знали верхнюю границучисла итераций (число элементов массива – верхняя граница числаитераций в задачах с досрочным выходом по условию).Рассмотрим ситуацию, когда число итераций нам действительнозаранее не известно.

В качестве примера можно взять типичную задачуиз численных методов по вычислению суммы бесконечного ряда сзаданной точностью. На практике подобная задача возникает принеобходимости вычисления интегралов.12Пример 4.4. «Вычислить интеграл ∫0 − с точностью = 0.01».Известно представление функции в виде ряда Маклорена для :− 24 6 2=1− +− + ⋯ + (−1)+ ⋯ , ∈ ℛ.2! 3!!2Почленное интегрирование ряда от 0 до 1 даст следующую сумму:1∫01− 24 6 2 = ∫ (1 − + − + ⋯ + (−1)+ ⋯ ) =2! 3!!20357 2+11= ( − +−+ ⋯ + (−1)+ ⋯)| .3 5 ∙ 2! 7 ∙ 3!(2 + 1) ∙ !012Воробьева И.А.

«Информатика. Язык Паскаль»Всего лишь первых четырех членов ряда достаточно, чтобы получитьзаданную точность :1∫ − ≈ 1 − 1⁄3 + 1⁄10 − 1⁄42 ≈ 0.7428620Так как ряд знакочередующийся, то модуль всего остатка бесконечной1 11суммы будет меньше пятого члена ряда, который равен ∙ =≈9 4!2160.00463 и очевидно меньше .Особенностью данной задачи является то, что число слагаемыхзаранее неизвестно, а суммирование должно завершиться в моментдостижения требуемой точности .Здесь наиболее уместно использовать итерационный цикл: в телецикла будет происходить суммирование очередного слагаемого, аусловие прекращения цикла – это сравнение очередного слагаемого сточностью . Таким образом, на каждом шаге вычислений витерационном цикле происходит последовательное приближение кискомому результату и проверка условия достижения последнего.Замечание 4.6.

Заданное условие окончания итераций цикла можетне достигнуть значения TRUE – истина, например, в суммированиирядов с плохой сходимостью. Поэтому, с точки зрения грамотногопрограммирования, в подобных циклах особенно важнорассмотреть ситуации возможного зацикливания (бесконечноговыполнения программой тела цикла.Если вы не можете гарантировать заранее выполнение условиявыхода из цикла, достаточно ввести специальную переменную Cnt –счетчик максимально допустимого выполнения циклов.При переполнении этого счетчика:23Воробьева И.А.

«Информатика. Язык Паскаль»1 зафиксировать ошибку: сообщение; установка так называемого флага ошибки в отдельнойвыделенной переменной Flg.2 обеспечить выход из цикла: ИЛИ принудительной установкой условия в состояние«истина»; ИЛИ, что гораздо лучше, включив сам счетчик в логическоеусловие окончания цикла.Подобные действия могут потребоваться в режимах отладки программногокода, отладки предложенного метода решения задачи и т.п.Вывод рекуррентного соотношенияДля того чтобы вычислить -й член последовательности (слагаемоеили множитель бесконечного ряда) используют так называемыерекуррентные вычисления.Рекуррентная формула (или рекуррентное соотношение) —формула, выражающая каждый член последовательности через предыдущих членов этой последовательности = (, −1 , −2 , .

. , − ).Замечание 4.7. Получение рекуррентной формулы далеко не всегдатривиальная задача.Иногда выгодно считать последовательность, начиная с индекса«0»: 0 ; 1 ; 2 ; . . . . .. , а не с индекса «1»: 1 ; 2 ; . . . … .Пусть p=1. Рекуррентную формулу могут искать в виде = (1, −1 ) = − ∙ ()(4.1)+ = (1, ) = ∙ ().(4.2)или в виде34Воробьева И.А. «Информатика. Язык Паскаль»Мы будем искать формулу в виде (4.1), так как исходя из практическогоопыта, в этом случае совершают меньше ошибок при выводе,проверке формулы и последующем ее кодировании.Рассмотрим вывод рекуррентнойконкретного бесконечного ряда.формулынапримереПример 4.5.

Решение задачи 1.5. «Вычисление функции разложениемее в ряд» (из задачника Котаровой).Известно, что часть функций могут быть представлены в видесуммы бесконечного ряда. Например, вычислить функцию 3 ∙3√1 + − 3 для | | < 1 с заданной точностью – равносильно:вычислить бесконечную сумму рядаS  x  62 x 2  6295 x 3  ...  256...9...3i3i 4  x i  ...(4.3)с точностью для | | < 1 (ряд (4.3) сходится при | | < 1).Обратите внимание, что знаки слагаемых чередуются, а степеньпеременной в числителях возрастает – это означает, что при | | <1 для данной бесконечной суммы требуемая точность будетдостигнута, когда очередное слагаемое станет по абсолютнойвеличине меньше , при этом абсолютная величина всехотброшенных членов ряда тоже оказывается меньше .Рассмотрим формулу (4.3) из задачи.

В ней можно вычислитьмножитель 1 (), умножением на который получается слагаемоеiго шага из слагаемого предыдущего (i-1)-го шага. () зависит от i –номера слагаемого в бесконечной сумме = ∑∞=1 . По формуле (4.1),получаем, что: () == (−1) ∙2∙5…(3(−1)−4)∙(3−4)∙ 6∙9…3∙(−1)∙3∙−1=6∙9…3∙(−1)2∙5…(3(−1)−4)∙ −1= −3−43.(4.4)45Воробьева И.А. «Информатика. Язык Паскаль»3−4Убедимся, что рекурсия = −1 ∗ (−1) ∙ верна. Выполним3проверку для второго и третьего слагаемого (проверку формулы всегдаделают для двух членов ряда минимум, для надежности):шаг i1i-й член ряда из формулы (4.3)1 = 23∙2−42= − 23∙2623∙3−42∙53 = 2 ∙ 1 (3) = − 2 ∙ (−)= 363∙36∙932 = 1 ∙ 1 (2) = ∙ (−)……Сравнение рекуррентныхформулам (4.1) и (4.2)соотношений,полученныхпоКак уже было сказано, рекуррентное соотношение можно получитьи по формуле (4.2): () == (−1) ∙+12∙5…(3−4)∙(3(+1)−4)∙ +16∙9…3∙3(+1)∙=6∙9…32∙5…(3−4)∙ = −3−13+3.шаг i1i-й член ряда из формулы (4.4)1 = 23∙1−12= − 23∙1+3623∙2−12∙53 = 2 ∙ 2 (2) = − 2 ∙ (−)= 363∙2+36∙93…(4.5)2 = 1 ∙ 2 (1) = ∙ (−)…Обратите внимание, что отличаются как формулы, так ифактический аргумент, который необходимо задать, для получения56Воробьева И.А.

«Информатика. Язык Паскаль»очередного члена ряда,одинаковым – это «».хотяформальныйаргументостаетсяРекуррентное соотношение в циклах с предусловием ипостусловиемДля рекуррентных вычислений можно с одинаковым успехомиспользовать и циклы с предусловием WILE и циклы с постусловиемREPEAT, однако надо правильно организовать обработку первогослагаемого и инициализацию основных величин цикла: i – номер слагаемого ряда; S_i – i-е слагаемое суммы ряда; Sum – частичная сумма (накапливает S_i).Покажем, как это сделать.Так как сравнение очередного члена ряда с заданной точностью нужно обеспечить, строго говоря, для всех слагаемых ряда, включаяпервое 1 , это значит, что в тело цикла с предусловием WILE попадуттолько шаги итераций, начиная с i=2, а переменная S_i должна бытьпроинициализирована значением первого слагаемого ряда – = 1 .Однако в цикле с постусловием REPEAT сравнение 1 с точностью можно произвести только после отработки тела цикла, а значитзначение первого слагаемого должно быть вычислено непосредственнов теле цикла на первом шаге итерации.Давайте посмотрим, какое начальное значение нужно присвоитьпеременной S_i, чтобы после применения к ней формулы (4.4) на шагеi=1, мы получили значение равное первому слагаемому ряда – (см.формулу 4.3).

Подставив в формулу (4.4) значение i=1, получим: − ∗3∗1−4= . Это означает, что достаточно положить в качестве начального3∗13значения переменной S_i: _ = 3.67Воробьева И.А. «Информатика. Язык Паскаль»В сравнительной таблице ниже, обратите внимание, что телациклов WILE и REPEAT полностью идентичны, однако инициализацияпеременных отличается.i – номерслагаемого рядаS_i - i-еслагаемое суммырядаSum – частичнаясумма(накапливает S_i)Для цикла WILE.Инициализация i:= 1;переменных:s_i:= x; // первоеслагаемоеsum:= s_i;Организацияцикла:«Пока» |s_i| >= «выполнять»i:= i+1; // переход кследующемуслагаемомуs_i:= (-1)*s_i*x*(3*i-4)/(3*i); // очередноеслагаемоеsum:= sum+s_i; //накапливаемчастичную сумму«конец цикла»Для цикла REPEAT.i:= 0;s_i:= 3; //корректирующаявеличина для полученияпервого слагаемогоравного «»sum:= 0;«Повторять»i:= i+1;s_i:= (-1)*s_i*x*(3*i-4) /(3*i);sum:= sum+s_i;«пока не» |s_i|< //пока не достигнем78Воробьева И.А.

«Информатика. Язык Паскаль»Программный код для вычисления суммы ряда (4.3) припомощи формулы (4.4) и цикла WILEprogram Func_Iter_Sum_Cons;CONSTeps= 0.00001; // точность вычисленияVARx: real;// аргумент сложной функцииS_i: real; // слагаемое частичной суммы Sum на i-м шагеSum: real; // накапливаемое значение суммы ряда,т.е. частичная суммаi: integer; // номер слагаемого в сумме – шаг итерацииFunc: real=0; // результат по проверочной формулеBEGINwriteln('Вычисление функции разложением ее в ряд.');writeln;writeln('Введите Х в диапазоне: -1 < X < 1:');write('X = ');readln(x);// ввод аргумента Xwriteln('x= ', x:9:4);readln;If (abs(x)<1)не// проверка, что Х введен правильно, иначе мы// сможем выйти из цикла (ряд не сойдется)thenbegin// вычислим сразу же контрольную формулу и выведем на экранFunc:= 3*exp((1/3)*Ln(1+x)) - 3;writeln('Контрольное значение функции = ',Func:9:5);//--- Блок инициализации перед вычислением ----------i:= 1;// первый шагs_i:= x;// первое слагаемое89Воробьева И.А.

«Информатика. Язык Паскаль»sum:= s_i; // Частичная сумма на первом шаге// равна первому слагаемомуwhile NOT (abs(s_i) < eps) do// если очередное слагаемое не// меньше тогда продолжим накопление суммы рядаbegini:= i+1;// увеличим номер слагаемогоs_i:= (-1)*s_i*(3*i-4)* x /(3*i); // очередное слагаемоеsum:= sum+s_i;// накапливаем частичную суммуend;writeln('Сумма ряда = ', sum:9:4);// вывод значения функции,// полученной с помощью суммы рядаendelsebeginwriteln('Допущена ошибка диапазона при вводе X. Нажмите ENTERдля завершения');end;readln;END.Вывод рекуррентного соотношения, когда член ряда – суммаслагаемыхРассмотрим вариант суммы ряда, когда слагаемые ряда являютсясоставными, вида ( ± ).

Например, функциисоответствует ряд111111!12!3(2)!( + ) − 2 ( + ) + ⋯ ± 2 (+1(2+1)())∓⋯+ ()(4.5)Ряд сходится при | | < 1 , а функция не определена для = 0.В рядах такого вида будем выводить рекуррентные соотношениядля каждой составляющей слагаемого отдельно:910Воробьева И.А. «Информатика. Язык Паскаль» = − ∙ (); = − ∙ ().и(4.6)Выведем формулу для ряда (4.5): () = () =−1−1= (−1) ∙ 2 (2−2)!∙(2)! 2−2 2= (−1) ∙ (2+1) ∙и сделаем проверку:шаг i0= −(2−1) 2−2(2−2)!2(2)∙(2−1)∙(2−2)!= − 2=−(2−1)(2+1)22∙(2−1);(4.7)i-й член ряда из формулы (4.3)110 = = 1; 0 = = 1;1!1(см. замечание 4.7)1221 = 0 ∙ (−1)=− ;2∙12!2 ∙ 121 = 0 ∙ (−1)=− ;3322242 = − ∙ (−1)= ;2!4 ∙ 3 4!22 ∙ 3 42 = − ∙ (−1)= ;344……Фрагмент кода для такого ряда будет выглядеть следующим образом://--- Блок инициализации перед вычислением ----------i:= 0;// первый шагa_i:= 1;// первое составное слагаемоеb_i:= 1;// второе составное слагаемоеsum:= a_i +b_i; // Частичная сумма на первом шагеwhile NOT (abs(a_i +b_i ) < eps) do// если очередноеслагаемое не меньше тогдапродолжим накопление суммы рядаbegini:= i+1;// увеличим номер слагаемогоa_i:= (-1)*a_i*sqr( x) /(4*sqr(i)-2*i);// очередное слагаемоеb_i:= (-1)*b_i*(2*i-1)*sqr( x) /(2*i+1);1011Воробьева И.А.

«Информатика. Язык Паскаль»sum:= sum + a_i +b_i ;// накапливаем частичную суммуend;Замечание 4.8. Рекомендации по выполнению лабораторнойработы.Использовать в условии прерывания цикла дополнительный счетчикдля защиты от зацикливания итераций.Использовать формулу 4.1. для вывода рекуррентного соотношения.Обязательно просчитать на калькуляторе значение контрольнойфункции при «хорошем числе» = 0.5, чтобы иметьгарантированную величину, по которой можно контролироватьправильность работы программы при отладке.Некоторые варианты: работают с последовательностями, начиная с индекса «0»:0 ; 1 ; 2 ; . . .