WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Програмування: рекурентні послідовності та співвідношення - Реферат

Програмування: рекурентні послідовності та співвідношення - Реферат


Реферат з інформатики
Програмування: рекурентні послідовності та співвідношення
1.Рекурсії.
Для обчислення степеня в алгоритмі накопичування добутку (див. П. 3.3) змінна p приймала значення 1, a, a2, a3, … , an. У цій послідовності перший член 1, а кожний наступний дорівнює попередньому, помноженому на a. Позначивши члени послідовності через p0, p1, p2, ... pn, маємо рівність: pi=pi-1*a при i=1,2,…,n. Така рівність, що виражає член послідовності через попередні (один або кілька), називається рекурентним співвідношенням.
"Рекурентний" означає "зворотний". Справді, елемент послідовності тут визначається через попередні, і для його обчислення треба повернутися до них. Усім добре відомі рекурентні співвідношення вигляду an=an-1+d або bn=bn-1* q - їм задовольняють члени відповідно арифметичних або геометричних прогресій. Конкретна ж прогресія, тобто послідовність чисел, задається першим членом a1 і різницею d (або знаменником q). Власне, послідовність степенів у прикладі p0, p1, p2, … - геометрична прогресія: вона визначається першим членом p0=1 і рекурентним співвідношенням pi=pi-1*a при будь-якому i>0. Послідовність, члени якої задовольняють деяке рекурентне співвідношення, також називається рекурентною.
Приклад . Розглянемо послідовність {f} чисел 1, 1, 2, 3, 5, 8, 13, … , у якій f1=f2=1, а наступні члени задаються рекурентним співвідношенням
fn=fn-2+fn-1, n>2.
Вона називається послідовністю чисел Фібоначчі - за прізвиськом Леонардо Пізанського, який першим її описав. За першими двома її членами можна обчислити третій. Для обчислення четвертого перший член уже не потрібний, тому що f4=f2+f3. Для обчислення п'ятого достатньо пам'ятати лише третій і четвертий тощо. Обчислюючи члени послідовності один за одним, ми дістанемося будь-якого, почавши з перших двох. При цьому щоразу ми використовуємо лише два останніх значення і, обчисливши наступне, "забуваємо" перше з двох використаних.
Нехай дано номер n, n>2, і треба обчислити fn. Опишемо ці обчислення. З попередніх міркувань випливає, що потрібні дві змінні для двох сусідніх членів і третя для наступного (назвемо їх fa, fb і fc), а також змінна m для зберігання номера останнього з обчислених членів.
Спочатку fa=1, fb=1, m=2, (*)
потім обчислимо fc:=fa+fb і збільшимо m на 1. Якщо значення fb і fc зробити відповідно значеннями fa і fb (fa:=fb, fb:=fc), то обчислення четвертого члена можна задати таким самим оператором fc:=fa+fb. Отже, поки mfc:=fa+fb, m:=m+1, fa:=fb, fb:=fc. (**)
Очевидно, що з кожним виконанням fc:=fa+fb, m:=m+1 ми переходимо до наступного члена послідовності і в m запам'ятовуємо його номер. Оскільки значення m щоразу зростає, зрештою виявиться, що m=n, умова mfa=1; fb=1; m=2;
while mbegin
fc:=fa+fb; m:=m+1;
fa:=fb; fb:=fc
end; {m=n, значення змінних fc і fb - шукане}
Відзначимо, що присвоювання fa:=fb та fb:=fc ні в якому разі не можна переставляти - можете про імітувати початок виконання цього алгоритму з переставленими присвоюваннями й переконатися, що значеннями змінної fc будуть аж ніяк не числа Фібоначчі.
У загальному випадку рекурентне співвідношення задає залежність члена рекурентної послідовності sn від k попередніх у вигляді деякого виразу sn=F(sn-k, … , sn-1). Число k називається порядком рекурентного співвідношення. Якщо відомі sn-k, ... , sn-1, то вираз F фактично задає обчислення sn. Назвемо це обчислення застосуванням рекурентного співвідношення.
Припустимо, нам відомо рекурентне співвідношення sn=F(sn-k, ... , sn-1) і перші k членів рекурентної послідовності. Треба за номером p обчислити sp. Знаючи перші k членів, можна застосувати до них співвідношення й обчислити sk+1; аналогічно за s2, ... , sk+1 обчислюється sk+2 тощо. Щоразу для обчислення чергового члена потрібні тільки k останніх із попередніх.
Отже, для опису цих обчислень потрібні:
k змінних для k останніх членів (нехай їх імена A, B, … , X),
змінна для нового члена (нехай її ім'я Y),
змінна M для номера останнього з обчислених членів.
Треба створити "деталі конструктора", тобто запрограмувати:
ініціалізацію змінних A, B, … , X першими k значеннями послідовності;
застосування рекурентного співвідношення, тобто обчислення нового члена й запам'ятовування його в змінній Y;
присвоювання значень змінних B, … , X, Y відповідно змінним A, B, … , X (назвемо це
переприсвоюванням).
Тоді розв'язання задачі має вигляд:
ініціалізація змінних A, B, … , X;
M:=k;
while умова продовження do
begin
присвоїти Y результат застосування рекурентного співвідношення до значень змінних A, B, … , X;
M:=M+1;
A:=B; ... ; X:=Y {переприсвоювання}
end
У нашому випадку умова продовження - це просто вираз MРозв'язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером). Там k=2 і використано імена fa, fb, fc замість A, ... , X, Y.
Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while.
Зауважимо, що якщо порядок рекурентного співвідношення k=1, то для обчислення нового члена може виявитися достатнім однієї змінної. Так було в перших задачах, де, наприклад, при виконанні p:=p*a спочатку за старим значенням змінної p обчислювалося нове й потім їй же присвоювалося. Проте далі ми наведемо приклади, де послідовність задається співвідношенням порядку 1, але в умові продовження обчислень
використовуються два останніх члени. Тому там будуть потрібні дві змінні.
Приклад 4.4. Античні греки вміли приблизно обчислювати за допомогою послідовності чисел, що сходиться до нього. За алгоритмом Герона така послідовність утворюється застосуванням рекурентного співвідношення
, починаючи з будь-якого додатного x1, наприклад, із x1=(a+1)/2. Однією з властивостей
послідовності є те, що 1.
Умови продовження обчислень можуть бути різними, наприклад, >d або >d для деякого d>0.
Розглянемо друге з них. Оскільки в ньому вказано два сусідніх члени, потрібні дві змінні для їх збереження,
причому обидві повинні мати різні значення вже перед першою перевіркою умови продовження. Після того, як
вона виявляється істинною, для обчислення нового члена передостанній член уже не потрібний, тому що
рекурентне співвідношення має порядок 1. Тому в тілі циклу треба спочатку вказати переприсвоювання, а потім
обчислення нового члена. Номера членів послідовності нас не цікавили, тому алгоритм має вигляд:
X:=(a+1)/2; Y:=0.5*(X+a/X);
while abs(X-Y)>d do
begin
X:=Y; Y:=0.5*(X+a/X);
end;
{ abs(X-Y)<=d, значення Y вважається шуканим, адже |Y-a| ||. Тому,
якщо додати всі члени від першого до останнього зтаких an, що |an|>d за деякого d>0, то одержана сума
відрізняється від sinx не більш, ніж на d.
Отже, треба обчислити sn=, де n невідомо, а відомо лише, що |an|>d, |an+1|? d. Очевидно,
sn=sn-1+an за будь-якого n>1, а s1=a1=x. Ці рівності виражають залежність значення суми від попередньої суми і
відповідного доданка, тобто послідовність значень сум рекурентна. Помітимо, що при d0.
Знайдемо рекурентне співвідношення для послідовності доданків , виразивши an через
an-1. Для цього у виразі для an побудуємо вираз, яким задається an-1:
=
= .
Отже, при n>1, a1=x. Запишемо одержані рекурентні співвідношення в систему:
Побудуємо за нею алгоритм обчислення. Оскільки порядок обох співвідношень 1, достатньо двох змінних, S і A,
для збереження членів послідовностей. Спочатку A:=x; S:=0. Далі перед кожним обчисленням S:=S+A треба
спочатку перевірити, що A>d. Після додавання A до S обчислюється новий доданок (значення A), і все
повторюється. Таким чином, цикл складений діями в такому порядку:
перевірка умови A>d,
додавання S:=S+A,
обчислення нового значення A.
Нехай змінна I зберігає номер останнього обчисленого доданка; спочатку I=1. Оскільки при обчисленні нового
доданка використовується його номер, то цей номер треба попередньо збільшити. Тепер алгоритм очевидний:
S:=0; A:=x; I:=1;
while A>d do
begin
S:=S+A; I:=I+1;
A:=A*(-x*x)/((2*I-2)*(2*I-1));
end
{A2. Шуканим є останнє ненульове
значення послідовності. Уточнити алгоритм Евкліда у вигляді функції.
4.6. Послідовність {xn}, задана співвідношеннями
x1=(a+m-1)/2,
xi=( (m-1)xi-1 + a/x)/m при i > 1,
сходиться до a1/m. Запрограмувати обчислення a1/m при довільному додатному дійсному a з точністю e , тобто за потрібне число
приймається перше xn таке, що | xn-xn-1 |4.7. Послідовність сум {sn}, де sn=1+x+x2/2!+…+xn/n!, за умови 0? x<1 "достатньо швидко" сходиться до ex. Запрограмувати
обчислення ex при x? [0;1) із точністю e , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |Запрограмувати обчислення ex при довільному x, застосовуючи "формули зведення" - рівності ex=e[x]e{x}, ex=1/e-x, де [x] і {x}
позначають цілу й дробову частини x. Обчислити e[x] шляхом множення сталої e=2.7182818 на себе [x] разів.
4.8. Послідовність сум {sn}, де sn=1-x2/2!+…+(-1)nx2n/(2n)!, за умови |x|? p /4 "достатньо швидко" сходиться до cos(x).
Запрограмувати обчислення cos(x) при x? [-p /4; p /4] з точністю e , тобто за потрібне число приймається перше sn таке, що |
sn-sn-1 |Запрограмувати обчислення cos(x) при довільному x, застосовуючи тригонометричні формули зведення.
Loading...

 
 

Цікаве