UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПрограмування: рекурентні послідовності та співвідношення (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось2432
Скачало309
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

хибною, і змінних fb і fc матимуть потрібне нам значення fn. Залишилося

перекласти на Паскаль рядки, відзначені (*) і (**):

 

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 ні в якому разі не можна

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ