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

Програмування: рекурентні послідовності та співвідношення
Тип документу: Реферат
Сторінок: 5
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 0
Скачувань: 947
{ abs(X-Y)<=d, значення Y вважається шуканим, адже |Y-a|
?

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

можуть бути виражені як члени рекурентних послідовностей. Треба:

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

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

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

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

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

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

чітко й точно, що ж саме повинно бути виконано. Рекурентні співвідношення якраз і дають точне вираження

необхідних дій та служать надійною основою для написання програми. Насмілимося запевнити читача, що

витрати часу на попереднє формулювання рекурентних співвідношень окупаються при написанні програми і

дозволяють уникнути багатьох помилок.

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

Є чимало задач, у розв'язанні яких використовуються не одна, а кілька рекурентних послідовностей. Члени

послідовності можуть залежати від попередніх членів як "своєї", так і інших послідовностей. Ці залежності записуються

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

1!, 2!, 3!, … залежать від їх номерів і попередніх членів. Але послідовність номерів сама рекурентна, оскільки кожний

номер на 1 більше попереднього.

Приклад 4.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 через

The online video editor trusted by teams to make professional video in minutes