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

присвоїти Y результат застосування рекурентного співвідношення до значень змінних A, B, … , X;

M:=M+1;

A:=B; ... ; X:=Y {переприсвоювання}

end

У нашому випадку умова продовження – це просто вираз M
Розв'язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером (приклад 4.3). Там k=2 і використано імена fa, fb, fc замість A, ... , X, Y.

Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while.

Зауважимо, що якщо порядок рекурентного співвідношення k=1, то для обчислення нового члена може виявитися достатнім однієї змінної. Так було в перших задачах, де, наприклад, при виконанні p:=p*a спочатку за старим значенням змінної p обчислювалося нове й потім їй же присвоювалося. Проте далі ми наведемо приклади, де послідовність задається співвідношенням порядку 1, але в умові продовження обчислень використовуються два останніх члени. Тому там будуть потрібні дві змінні.

Використання рекурентних співвідношень дозволяє легко програмувати розв'язання задач, де шукані величини можуть бути виражені як члени рекурентних послідовностей. Треба:

•зрозуміти, що розв'язання задачі можна побудувати на використанні рекурентної послідовності;

•записати відповідне рекурентне співвідношення;

•визначити перші члени послідовності, що обчислюються без застосування співвідношення;

•сформулювати умову, за якої треба продовжувати застосування рекурентного співвідношення.

Після цього згадані вище "деталі конструктора" та порядок їх розташування в алгоритмі стають очевидними.

Програма – це абсолютно точний опис дій, які треба виконати. Її неможливо написати, не сформулювавши чітко й точно, що ж саме повинно бути виконано. Рекурентні співвідношення якраз і дають точне вираження необхідних дій та служать надійною основою для написання програми. Насмілимося запевнити читача, що витрати часу на попереднє формулювання рекурентних співвідношень окупаються при написанні програми і дозволяють уникнути багатьох помилок.

2.2. Системи рекурентних співвідношень

Є чимало задач, у розв'язанні яких використовуються не одна, а кілька рекурентних послідовностей. Члени послідовності можуть залежати від попередніх членів як "своєї", так і інших послідовностей. Ці залежності записуються у вигляді систем рекурентних співвідношень. Насправді, ми вже бачили зв'язані послідовності: члени послідовності 1!, 2!, 3!, … залежать від їх номерів і попередніх членів. Але послідовність номерів сама рекурентна, оскільки кожний номер на 1 більше попереднього.

Задачі

4.* Написати функцію обчислення кількості десяткових цифр натурального числа.