[ЗМІСТ] [Далі] [Назад]

3.2. Програмування рекурентних співвідношень

3.9. Скласти алгоритми для обчислення елементів послідовностей

а) ; д) ;

б) ; е) ;

в) ; ж) ;

г) ; з) .

Розв`язок г) Складемо рекурентне співвідношення для обчислення x_k

x₀=x, x_k=, k=1,2...

Передбачивши введення і виведення, отримаємо

алг Рекур це

змін х,у:дійсн;

і,п:нат;

поч

взяти (х,п);

у¬1;і¬0;

повт п раз

і¬і+1;

у¬у*х/і

кц;

показати (у)

ка.

3.10. Числами Фібоначчі називається числова послідовність {F_n}, задана рекурентним співвідношенням другого порядку

F₀=0; F₁=1; F_k=F_k-1+F_k, k=2,3,...

Скласти алгоритм для обчислення F_n

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

Алг Фібоначчі це

змін n,f,sf,t:нат;

поч

взяти (п);

f¬0;sf¬1;

{f =F₀, sf =F₁}

повт п раз

t¬f+sf;

f¬sf;sf¬t

кц;

{f =F_n, sf=F_n+1}

показати (f)

ка.

3.11. Скласти алгоритм обчислення довільного члена послідовностей, які задані рекурентними співвідношеннями:

а) x_n=x_n-1+x_n-3, x₀=x₁=1, x₂=2, n=3,4,...;

б) x_n=2x_n-1+3x_n-2, x₀=0, x₁=9, n=2,3,...;

в) x_n=x_n-1+x_n-2+x_n-3, x₀=x₁=1, x₂=6, n=3,4,...;

г) x_n=x_n-1+4x_n-3, x₀=x₁=x₂=2, n=3,4,...;

д) x_n=x_n-1*(x_n-2+1), x₀=1, x₁=1, n=2,3,...;

е) x_n=, x₀=0, x₁=, n=2,3,...;

3.12. Скласти алгоритми для обчислення сум:

а) S_n=;

б) S_n =;

в) S_n =;

г) S_n =;

д) S_n =1-2-3+4-5-6+...+(3n-2)-(3n-1)-3n;

е) S_n =1+2+3+...+n; ж) S_n =a+2a²+3a³+...+naⁿ;

з) S_n =; і) S_n =; к) S_n =;

л) S_n =; м) S_n =; н) S_n =;

о) S_n =; п) S_n =.

Вказівки. Суму S_n обчислити за допомогою рекурентного співвідношення S₀=0, S_k=S_k-1+a_k, k=1,2,...n, де a_k - k-тий доданок.

з) S_i=2S_i-1+i²; і) S_n =2ⁿ; л) S_n =; м) a_k =2ka_k-1.

3.13. Скласти алгоритми для обчислення добутків:

а) ; б) ;

в) ; г) .

Вказівка. Добуток P_n обчислити за допомогою рекурентного співвідношення P₀=1; P_k=P_k-1*a_k, k=1,2,...,n, де a_k - k- тий множник.

3.14. Скласти алгоритми для обчислення ланцюгових дробів

а) ;

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

а) b₀=b, b_k=b+, k=1,2,...n;

в) b₀=4n+2, b_k=4(n-k)+2+, k=1,2,...n.

3.15. Скласти алгоритми для обчислення

а) многочлена Чебишова

T₀(x)=1, T₁(x)=x,

T_n(x)=2xT_n-1(x) - T_n-2(x), n=2,3,...;

б) многочлена Ерміта

H₀(x)=1, H₁(x)=2x,

H_n(x)=2xH_n-1(x) - 2(n-1)H_n-2(x), n=2,3,...

заданого степеню n в точці х.

3.16. Скласти алгоритм обчислення довільного елемента послідовностей, заданих рекурентними співвідношеннями

а) v₀=1,v₁=0.3, v_i=(i+2)v_i-2 , i=2,3,...

б) v₀=v₁=v₂=1, v_i=(i+4)(v_i-1 - 1)+(i+5)v_i-3 , i=3,4,...

в) v₀=v₁=0,v₂=, v_i=, i=3,4,...

3.17. Скласти алгоритм обчислення довільного елемента послідовності v_n, визначеної системою співвідношеннь

v₀=v₁=1, v_i = , i=2,3,..;

де u₀=u₁=0 , u_i = , i=2,3,... .

3.18. Скласти алгоритм для обчислення сум

а) S_n =, де a₁=0, a₂=1, a_k=a_k-1+k*a_k-2, k=3,4,...;

б) S_n =, де a₁=1, a₂=1, a_k= , k=3,4,...;

в) S_n =, де a₁=1, a₂=1, a_k=, k=3,4,...;

г) S_n =, де a₁=0, a₂=1, a_k=a_k-1+, k=3,4,...;

д) S_n =, де a₁=a₂=a₃=1, a_k=a_k-1+a_k-3, k=4,5,...;

е) S_n =, де a₀=1, a_k=ka_k-1+, k=1,2,...

Вказівка. Позначимо загальний член ряду через b_k. Послідовність а_k задається залежностями вигляду (R₁) для е), (R₂) для а)--г) та (R₃) для д); S_k=g(S_k-1, b_k). Значення а_k будуть обчислюватись за теоремами 1-2. Для обчислення послідовновності S_k цикли доповнюються однією змінною.

Розв`язок д). Вводячи допоміжну змінну для обчислення 2^k і використовуючи рекурентні співвідношення t₀=1, t_k=2t_k-1, k=2,3,.. для знаходження цієї системи отримаємо алгоритм

алг Сума це

змін u , v, w, t, r, s: дійс;

n: нат;

поч

взяти (n);

u¬1; v¬1; w¬1; t¬1; s¬0;

{ u=a₁, v=a₂, w=a₃ }

повт n раз

t¬t*2;

s¬s+u/t;

r¬u+w; u¬v; v¬w; w¬r

кц;

показати (s)

ка.

3.19. Скласти алгоритми для обчислення сум

а) S_n =,

де , ; k=3,4,...;

б) S_n =,

де ; ; k=2,3,...;

u,v - задані дійсні числа;

в) S_n =,

де ; ; k=2,3,...;

г) S_n =,

де ; ; k=2,3,...;

д) S_n =,

де ; ; k=1,2,... .

Розв`язок д). Послідовності {a_n} і {b_n} задані рекурентним співвідношеннями першого порядку, проте залежність перехресна. Використовуємо по одній допоміжній змінній для кожної з послідовностей. Отримаємо алгоритм

алг Сума це

змін a, b, aa, bb, s:дійс;

n:нат;

поч

взяти (n);

a¬1; b¬1; s¬0,5;

повт n раз

aa¬a*b; bb¬a+b;

a ¬aa; b¬bb; s¬s+a/(1+b)

кц;

показати (s)

ка.

Неважко побачити, що змінну bb легко виключити.

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

а) , де , k=3,4,...;

б) ,

де , k=2,3,... .

Розв`язок а) Послідовність {a_n} задана рекурентним співвідношенням третього порядку. Для обчислення її довільного елемента a_k використаємо теорему 2. Тоді добуток P_n обчислюється за допомогою рекурентного співвідношення P₀=1, P_k=P_k-1*, де z_k -- к-тий степінь числа 3, визначений із співвідношень z₀=1, z_k=z_k-1*3. Передбачивши також змінну t для обчислення степеня 2^к-1, отримаємо алгоритм

алг Добуток це

змін a0, a1, a2, w, p, z, t:дійсн;

n:нат;

поч

взяти (n);

a0¬1; a1¬1; a2¬3; z¬1; p¬1; t¬2;

повт n раз

z¬z*3; p¬p*a1/z;

t¬t*2;

w¬a0+a1/t;

a0¬a1; a1¬a2; a2¬w

кц;

показати (p)

ка.

[ЗМІСТ] [Далі] [Назад]