Програмування: рекурентні послідовності та співвідношення, Детальна інформація

Реферат з інформатики

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

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. Отже, поки m
fc:=fa+fb, m:=m+1, fa:=fb, fb:=fc. (**)

Очевидно, що з кожним виконанням fc:=fa+fb, m:=m+1 ми переходимо до наступного члена послідовності і в m запам'ятовуємо його номер. Оскільки значення m щоразу зростає, зрештою виявиться, що m=n, умова m
fa=1; fb=1; m=2;

while m
begin

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 (назвемо це