Цикл "поки" та його використання

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;

{ abs(X-Y)<=d, значення Y вважається шуканим, адже |Y-a|


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

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

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

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

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

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

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

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

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

Приклад 5. Значення функції sinx виражається у вигляді нескінченної суми: sinx= . При |x| 1 кожний доданок an, n 1, цієї суми за модулем менше попереднього. Крім того, |an| > | |. Тому, якщо додати всі члени від першого до останнього з таких an, що |an|>d за деякого d>0, то одержана сума відрізняється від sinx не більш, ніж на d.

Отже, треба обчислити sn= , де n невідомо, а відомо лише, що |an|>d, |an+1| d. Очевидно, sn=sn-1+an за будь-якого n>1, а s1=a1=x. Ці рівності виражають залежність значення суми від попередньої суми і відповідного доданка, тобто послідовність значень сум рекурентна. Помітимо, що при d<|x| доданок a1 не треба додавати до суми, і результатом повинна бути "сума без доданків". Тому до послідовності сум додамо s0=0; тепер sn=sn-1+an для n>0.

Знайдемо рекурентне співвідношення для послідовності доданків , виразивши an через an-1. Для цього у виразі для an побудуємо вираз, яким задається an-1: