ПАСКАЛЬ: ЦИКЛ "ПОКИ" ТА ЙОГО ВИКОРИСТАННЯ

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 (назвемо це переприсвоюванням).

Тоді розв'язання задачі має вигляд:

ініціалізація змінних A, B, … , X;

M:=k;

while умова продовження do

begin