[ЗМІСТ] [Далі] [Назад] [Початок розділу]

3.2. Рекурентні співвідношення

Виконавець AB, з пристроєм керування (С+IF+Ln), є ідеальним засобом для обчислення членів числових послідовностей, заданих рекурентними співвідношеннями.

3.2.1. Співвідношення першого порядку

Розглянуті в попередньому розділі приклади показують зразки послідовностей, які можна задати рекурентно. Дійсно, величина у_n = хⁿ визначається співвідношеннями

у = 1;

0

у = у *х; n = 1,2,...

n n-1

А величина u_n = n! - співвідношеннями

u = 1;

0

u = u *n; n = 1,2,...

n n-1

Арифметичний цикл дає стандартний спосіб обчислення послідовностей, заданих рекурентно.

Нехай числова послідовність а , а , ..., а , ..., задана співвідношеннями

0 1 k

------------------------------------

¦ а = с, ¦ (R )

¦ 0 ¦ 1

¦ а = f(k, а , р), k = 1,2,... ¦

¦ k k-1 ¦

L-----------------------------------

де с - числова константа, р - постійний параметр, f - функція, задана аналітично у вигляді арифметичного виразу, що складається з операцій, доступних операційному пристрою.

У першому з приведених вище прикладів f(k, b, р) = b*р, в іншому - f(k, b, р) = k*b.

Дамо спосіб обчислення а_n за довільним заданим n.

Теорема 3.1. (Перша теорема про рекурентні співвідношення).

При позначеннях (R₁) і довільному n

{k=0 & х=с}

повт n раз

k <- k+1;

х <- f(k, х, р)

кц

{k=n & х=а }.

n

Доведення проводимо методом математичної індукції.

а) При n=0 твердження очевидне.

b) Зробимо припущення

{k=0 & х=с}

повт n-1 раз

k <- k+1;

х <- f(k, х, р)

кц

{k=n-1 & х=а }.

n-1

c) Нехай n>0. Відмітимо, що

{k=n-1 & х=а }

n-1

k <- k+1;

х <- f(k, х, р)

{k=n & х=а }.

n

Сумістивши це з припущенням, маємо

{k=0 & х=с}

повт n-1 раз

k <- k+1;

х <- f(k, х, р)

кц;

{k=n-1 & х=а }

n-1

k <- k+1;

х <- f(k, х, р)

{k=n & х=а },

n

що безпосереднім застосуванням наслідку 3.1 виливається в шукане

{k=0, х=с}

повт n раз

k <- k+1;

х <- f(k, х, р)

кц

{k=n & х=а }.¦

n

Наслідок 3.3. Якщо вираз для а_k в (R₁) не залежить від k, тобто а_k = g(а_k-1,р), то для довільного n

{х=с}

повт n раз

х <- g(х, р)

кц

{х=а }.¦

n

Приклад 3.4. Побудувати алгоритм для обчислення

n

n х

t = (- 1) -----, n = 0,1,2,...

n n!

Спочатку знайдемо співвідношення. Маємо t₀ = 1. Розділивши t_k на t_k-1, отримаємо t_k = - t_k-1*х/k, k=1,2,.... Застосувавши теорему 3.1 і передбачивши введення даних та ініціалізацію змінних, отримаємо

Алгоритм Тn це

змін X, Т: дійсн;

k, n: нат;

поч

взяти (X, n);

k <- 0; Т <- 1;

{k=0 & Т=1}

повт n раз

k <- k+1;

Т <- -T*X/k

кц;

{k=n & Т=t }

n

показати (Т)

ка.

Приклад 3.5. На вході n чисел. З'ясувати, чи всі вони позитивні.

Визначимо числа, що вводяться як а₁, а₂, ..., а_n. Очевидно, нас цікавить умова Q=(а₁ >0) & (а₂ >0) &...& (а_n >0).

Розглянемо бульову послідовність

Q = Іст;

0

Q = Q & (а >0), k=1,2,..., n.

k k-1 k

Тоді Q_n = Q. Обчислення Q_n проведемо звичайним образом.

Алг Positive це

змін А: дійсн;

N: нат; Q: бул;

поч

взяти (N);

Q <- Іст;

повт N раз

взяти (А);

Q <- Q & (А>0)

кц;

показати (' Те, що всі числа позитивні, є', Q)

ка.

3.2.2. Співвідношення вищих порядків

Арифметичний цикл можна застосовувати також тоді, коли член послідовності залежить не від одного, а від декількох попередніх членів. Їх кількість називають порядком рекурентного співвідношення. Як приклад, розглянемо співвідношення третього порядку, хоч метод, який ми будемо використовувати, може бути застосований до будь-якого порядку. Важливо зазначити, що число змінних на одиницю більше порядку співвідношення.

Нехай, наприклад, послідовність х_n задана співвідношенням вигляду

------------------------------------------

¦ х = a, ¦

¦ 0 ¦

¦ х = b, ¦

¦ 1 ¦ (R )

¦ х = с, ¦ 3

¦ 2 ¦

¦ х = f(х ,х ,х ), k = 3,4,... ¦

¦ k k-3 k-2 k-1 ¦

L-----------------------------------------

де a, b і с - константи, f - функція, задана аналітично у вигляді арифметичного виразу.

Справедлива

Теорема 3.2. (Друга теорема про рекуррентні співвідношення).

Нехай послідовність {х_n} визначена за схемою (R₃).

Тоді при довільному натуральному n справедливе твердження

{u=a & v=b & w=с}

повт n раз

t <- f(u, v, w);

u <- v; v <- w; w <- t

кц

{u=х & v=х & w=х }.

n n+1 n+2

Доведення, майже дослівно попередньому, виконуємо індукцією по n.

a) При n=0 все очевидно.

b) Допустимо, що

{u=a & v=b & w=с}

повт n-1 раз

t <- f(u, v, w);

u <- v; v <- w; w <- t

кц

{u=х & v=х & w=х }.

n-1 n n+1

c) Нехай тепер n>0. Звернемо увагу на спосіб зміни значень u, v, w. Вони рухаються один за іншим вздовж елементів послідовності, тобто

{u=х & v=х & w=х }

n-1 n n+1

t <- f(u, v, w);

u <- v; v <- w; w <- t

{u=х & v=х & w=х }.

n n+1 n+2

Доказом може служити така таблиця

u v w t

-----------------------------

х ¦ х ¦ х ¦ ¦

n-1 ¦ n ¦ n+1 ¦ ¦

-----------------------------

t <- f(u, v, w) ¦ ¦ ¦ х ¦

¦ ¦ ¦ n+2 ¦

-----------------------------

u <- v х ¦ ¦ ¦ ¦

n ¦ ¦ ¦ ¦

-----------------------------

v <- w ¦ х ¦ ¦ ¦

¦ n+1 ¦ ¦ ¦

-----------------------------

w <- t ¦ ¦ х ¦ ¦

¦ ¦ n+2 ¦ ¦

-----------------------------

Сумістивши індуктивне припущення з останнім твердженням і застосувавши наслідок 3.1 відразу отримаємо необхідне.

Один крок циклу зображено на мал. 3.2.¦

------- u ---- v ---- w ----------------

... ¦ х ¦ х ¦ х ¦ х ¦ ...

¦ n-1 ¦ n ¦ n+1 ¦ n+2 ¦

----------------------------------------

^ ^ ^

u v t, w

МАЛ. 3.2.

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

Вправа 3.1. (Скорочення повторень). Довести, що при будь-якому n=2,3,... для послідовності (R₃)

{ u=a & v=b & w=с }

повт n-2 раз

t <- f(u, v, w);

u <- v; v <- w; w <- t

кц,

{ w=х }

n

тобто, якщо відомо, що n>1, число повторень циклу можна зменшити на 2, вважаючи результатом значення w або t.

Приклад 3.6. Розглянемо послідовність, названу числами Фібоначчи (Леонардо Пізанський, біля 1170-1228). Вона задана співвідношенням другого порядку

F = 0,

0

F = 1,

1

F = F + F, k = 2,3,...

k k-1 k-2

Якщо змінна f буде пробігати послідовність Фібоначчи, то двох додаткових змінних sf і t буде досить для позначення подальших двох чисел.

f <- 0; sf <- 1;

{f=F & sf=F }

0 1

повт n раз

t <- f+sf;

f <- sf; sf <- t

кц

{f=F & sf=F }.

n n+1

Висновок 3.1. З теореми 3.1 слідує висновок, що для отримання деякого елемента послідовності, заданої рекурентним співвідношенням першого порядку, досить однієї змінної, значення якої пробігають послідовність, що обчислюється. У свою чергу, теорема 3.2 показує, що якщо послідовність задана рекурентним співвідношенням k-го порядку (k>1), то для знаходження n-го елемента послідовності (n>=k) потрібно k+1 змінна.¦

Зауваження 3.2. Якщо за схемою теореми 3.2 дослівно побудувати цикл для (R₁), то в умовах наслідку 3.3 його тіло прийняло б вигляд

t <- g(х, р); х <- t.

Змінна t звідси очевидно забирається.¦

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

Метод обчислень, приведений в теоремах 3.1 і 3.2, легко узагальнити на системи співвідношень. Розглянемо деякі приклади, кожний з яких є типовим для свого класу співвідношень.

Приклад 3.7. Перевірити, що більше n! або аⁿ. Використовуючи алгоритми з прикладів 3.2 і 3.3 отримаємо

Алг FactPower це

змін А, X, Y: дійсн;

N, K: нат; С: бул;

поч

взяти (А, N);

X <- 1; Y <- 1; K <- 0;

повт N раз

K <- K+1;

Y <- Y*K; X <- X*А

кц;

С <- Y>Х;

показати (' Те, що факторіал більше степені, є', С)

ка.

Приклад 3.8. Побудувати алгоритм обчислення суми

k

n k х

S = å (- 1 ) ----.

n k=0 k!

Послідовності t_k і S_k можна визначити співвідношеннями

t = 1, t = -t *х/k,

0 k k-1

S = t , S = S + t , k = 1,2,...

0 0 k k-1 k

Тут t задане залежністю вигляду (R ), S = g(S ,t ). Величини t

k 1 k k-1 k k

будемо обчислювати по теоремі 3.1; доповнимо цикл однією змінною і, відповідно, одним присвоєнням для обчислення послідовності S_k. Маємо цикл

{t=1 & k=0 & S=1}

повт n раз

k <- k+1;

t <- -t*х/k; S <- S+t

кц

{t=t & S=S & k=n},

n n

який стандартним чином доповнюється до повного тексту алгоритму.

Помітимо, що S залежить від t , тому t знаходять першим.

k k k

Приклад 3.9. Скласти алгоритм обчислення значення виразу

k i n i

S = å х + å у, k, n>=2.

i=1 i=1

Очевидно, що S=S₁ +S₂ . Для обчислення S_j, j=1,2 скористаємося співвідношенням з прикладу 3.8 і алгоритмом з прикладу 3.2. Отримаємо

S1 <- 0; S2 <- 0; xi <- 1; yi <- 1;

повт k раз

xi <- xi*х; S1 <- S1+xi

кц;

повт n раз

yi <- yi*у; S2 <- S2+yi

кц;

S <- S1+S2.

Тут використовується 5 допоміжних змінних. Для виконання алгоритму необхідно здійснити 2(k+n)+1 операцій додавання і множення. При цьому цикли ініціюються k+n раз.

Модифікуємо алгоритм, щоб використовувалося менше змінних:

S <- 0; xi <- 1;

повт k раз

xi <- xi*х; S <- S+xi

кц;

xi <- 1; { дуже важлива команда }

повт n раз

xi <- xi*у; S <- S+xi

кц.

Тепер використовується тільки 2 допоміжні змінні. Арифметичних операцій потрібно 2(k+n), а цикли ініціюються також k+n раз.

Складемо ще один варіант алгоритму.

S <- 0; xi <- 1; yi <- 1;

якщо k>n то

l <- n; m <- k

інакше

l <- k; m <- n

кр; { l=min(k, n) & m=max(k, n) }

повт l раз

xi <- xi*х; yi <- yi*у; S <- S+xi+yi

кц;

повт m-l раз

якщо m=k то

xi <- xi*х; S <- S+xi

інакше

yi <- yi*у; S <- S+yi

кр

кц.

Тут використовується також 5 допоміжних змінних і 2(k+n) арифметичних операцій. Однак цикли ініціюються всього m = max(k, n) раз.

Вправа 3.2. Скласти варіант останнього алгоритму, що не використовує додаткову змінну m.

Приклад 3.10. Знайти суму

S = F + F +. .. + F

n 0 1 n

перших n чисел Фібоначчи.

Алгоритм з прикладу 3.6 доповнюється додатковою змінною і додатковим присвоєнням так само, як розглянуто в прикладі 3.8.

f <- 0; sf <- 1;

S <- 0;

{f=F & sf=F & S=S }

0 1 0

повт n раз

t <- f+sf;

f <- sf; sf <- t;

S <- S+f

кц

{f=F & sf=F & S=S }.

n n+1 n

Приклад 3.11. Послідовності {а_n} і {b_n} задані системою співвідношень

а = 1; b = 2;

0 0

а = а + b; b = а * b; k = 1,2,...

k k-1 k-1 k k-1 k-1

Хоч кожне співвідношення має тут перший порядок, але застосувати теорему 3.1 не можна, тому що залежність перехресна. Слід скористатися зауваженням 3.2. Будемо мати по одній допоміжній змінній для кожної з послідовностей

а <- 1; b <-2;

{а=а & b=b }

0 0

повт n раз

aa <- а+b; bb <- а*b;

а <- aa; b <- bb

кц

{а=а & b=b }

n n

Нескладний аналіз показує, що одну із змінних (яку?) можна забрати.

Приклад 3.12. Обчислити суму

k

n 2

S = å ---------,

k=1 а + b

k k

де а =0, а =1, b =1, b =1,

1 2 1 2

а =а /k + а *b , b =b +а , k=3,4,...

k k-1 k-2 k k k-1 k-1

Алгоритм має вигляд:

Алгоритм Sum це

змін А, A1, A2, В, B1, B2, X, S: дійсн;

K, N: нат;

поч

взяти (N);

A1 <- 0; A2 <- 1; B1 <- 1; B2 <- 1;

S <- 0; K <- 2; X <- 1;

повт N раз

K <- K+1; X <- 2*Х;

S <- S+Х/(A1+B1);

У <- A2+B2; А <- A2/K+A1*В;

A1 <- A2; A2 <- А; B1 <- B2; B2 <- В;

кц

показати (' Сума рівна ', S)

ка.

[ЗМІСТ] [Далі] [Назад] [Початок розділу]