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

переприсвоюванням).

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

ініціалізація змінних 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. Однією з властивостей

послідовності є те, що < при n>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;