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

 

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

 

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

 

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

 

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

у = 1;

0

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

n n-1

А величина un = 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. (Перша теорема про рекурентні співвідношення).

При позначеннях (R1) і довільному 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 в (R1) не залежить від k, тобто аk = g(аk-1,р), то для довільного n

{х=с}

повт n раз

х <- g(х, р)

кц

{х=а }.

n

 

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

n

n х

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

n n!

Спочатку знайдемо співвідношення. Маємо t0 = 1. Розділивши tk на tk-1, отримаємо tk = - tk-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 чисел. З'ясувати, чи всі вони позитивні.

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

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

 

Q = Іст;

0

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

k k-1 k

 

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

 

Алг 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} визначена за схемою (R3).

Тоді при довільному натуральному 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,... для послідовності (R3)

{ 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 дослівно побудувати цикл для (R1), то в умовах наслідку 3.3 його тіло прийняло б вигляд

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

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

 

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

 

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

Приклад 3.7. Перевірити, що більше n! або а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!

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

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; доповнимо цикл однією змінною і, відповідно, одним присвоєнням для обчислення послідовності Sk. Маємо цикл

{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=S1 +S2 . Для обчислення Sj, 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} і {bn} задані системою співвідношень

а = 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)

ка.

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