Програмування: рекурентні послідовності та співвідношення, Детальна інформація
Програмування: рекурентні послідовності та співвідношення
Тип документу: Реферат
Сторінок: 5
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 9.7
Скачувань: 1081
{ 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 через
?
Використання рекурентних співвідношень дозволяє легко програмувати розв'язання задач, де шукані величини
можуть бути виражені як члени рекурентних послідовностей. Треба:
зрозуміти, що розв'язання задачі можна побудувати на використанні рекурентної послідовності;
записати відповідне рекурентне співвідношення;
визначити перші члени послідовності, що обчислюються без застосування співвідношення;
сформулювати умову, за якої треба продовжувати застосування рекурентного співвідношення.
Після цього згадані вище "деталі конструктора" та порядок їх розташування в алгоритмі стають очевидними.
Програма – це абсолютно точний опис дій, які треба виконати. Її неможливо написати, не сформулювавши
чітко й точно, що ж саме повинно бути виконано. Рекурентні співвідношення якраз і дають точне вираження
необхідних дій та служать надійною основою для написання програми. Насмілимося запевнити читача, що
витрати часу на попереднє формулювання рекурентних співвідношень окупаються при написанні програми і
дозволяють уникнути багатьох помилок.
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
© Referats, Inc · All rights reserved 2021