ЦИКЛІЧНІ ПРОГРАМИ

3.1 Арифметичний цикл

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

а)  , n - натуральне число;

б)  , n - натуральне число;

в)  , n - ціле число.

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

а)  y=sin(sin(...sin(x)...))   (n раз);               б) y=sinⁿx.

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

          a*b*a*b*...*a*b*a  (2n знаків множення).

          3.4. Скласти алгоритми для обчислення значень многочленів і виконати їх при заданих значеннях аргументів:

а)  y = xⁿ+x^n-1+...+x²+x+1,                                   n=3, x=2;

б)              n=4,x=1;

в)               n=3,x=1;    

г)         n=4,x=1,y=2;

д)                               n=5,x=-1.

          Розв`язок а) Розглянемо два способи розв`язування.

Спосіб 1. Позначимо z^k=x_k. Тоді цикл

                   z¬1;

                   повт п раз

                             z¬z*x

                   кц

забезпечить послідовне обчислення z₀, z₁, ... , z_n. Передбачивши підсумо­вування, введення і виведення, отримаємо

                   алг Многочлен_1 це

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

                                      п:нат;

                   поч

                             взяти (п,х);

                             z¬1;у¬1;

                             повт п раз

                                      z¬z*х ; у¬у+z

                             кц;

                             показати (у)

                   ка.

Спосіб 2. Розставивши дужки наступним чином

= xⁿ+x^n-1+...+x²+x+1= (...(x+1)x+1)x+...+1)x+1,

отримаємо алгоритм

                   алг Многочлен_2 це

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

                                      п:нат;

                   поч

                             взяти (п,х);

                             у¬1;

                             повт п раз

                                      у¬у*х+1

                             кц;

                             показати (у)

                   ка.

          Трасувальна таблиця алгоритму приведена в табл. 3.1.

Таблиця 3.1. Трасувальна таблиця до завдання 3.4 а)

	х	п	у	коментар
взяти(п,х)	2	3
у¬1			1	у+1
повт 3 рази
1) у¬у*х+1			3	у=х+1
2) у¬у*х+1			7	у=
3) у¬у*х+1			15	y=
кінець_циклу
показати(у)			15

          Вказівка б). Цикл повт п раз х¬х*х кц забезпечує послідовне обчислення степенів .

          Вказівка д). .

          3.5. Скласти алгоритм обчислення добутку p=m*n, використо­вуючи операцію додавання та виконати його при т=5, п=3.

          3.6. Скласти алгоритм обчислення факторіалу

                   р=п!

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

а)   (п коренів),

б)  .

          3.8. Скласти алгоритми обчислення значень многочлена

а)  y = nx^n-1+(n-1)x^n-2+...+2x+1;

б)  у = xⁿ(1-x)^m, (n,m³0);

в)  .

 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)

                   ка.

3.3. Цикли за умовою

          3.21. Для довільного цілого числа m>1 знайти найбільше ціле k, при якому 4^k<m.

          3.22. Для заданого натурального числа n одержати найменше число вигляду 2^r, яке перевищує n.

          3.23. Визначити із скількох від`ємних чисел починається задана послідовність чисел.

          3.24. Задана непорожня послідовність ненульових цілих чисел, за якою йде 0. Визначити кількість змін знаку в цій послідовності. Наприклад, у послідовності 1, -34, 8, 14, -5, 0 знак змінююється три рази.

          Розв`язок .

          алг Зміна_Знаку_2 це

                   змін k:нат ;

                             a,x:ціл;

          поч

                   взяти(x,a); k¬0;

                   {цикл за умовою повторення}

                   поки a<>0  повт

                             якщо a*x<0 то k¬k+1 кр ;

                             x¬а; взяти (а)

                   кц;

                   показати(k)

          ка.

          Замінимо цикл з умовою повторення відповідно на цикл з умовою закінчення та цикл з виходом. Модифіковані алгоритми приймуть вигляд

          алгоритм Зміна _Знаку_2 це

                   змін k:нат;

                             a,x:ціл;

          поч

                   взяти(x,a); k¬0;

                   {цикл з умовою закінчення}

                   якщо a<>0 то

                             повт

                                      якщо a*x<0 то k¬k+1 кр;

                                      x¬a; взяти(a)

                             до a=0

                             кц

                   кр;

                   показати(k)

          ка.

          алгоритм Зміна_Знаку_3 це

                   змін k:нат;

                             a,x:ціл;

          поч

                   взяти(x,a);k¬0;

                   {цикл з виходом}

                   цикл

                             якщо a=0 то вихід ;

                             якщо a*x<0  то  k¬k+1 кр;

                             x¬a; взяти(a)

                   кц;

                   показати(k)

          ка.

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

          3.26. Дана непорожня послідовність різних дійсних чисел, серед яких є хоча б одне від`ємне число, за якою йде 0. Визначити величину найбільшого серед від`ємних членів цієї послідовності.

          3.27. Маємо дійсне число a. Скласти алгоритми обчислення:

а)  серед чисел   першого, більшого за a;

б)  такого найменшого n, що  

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

а)  номера найбільшого числа Фібоначчі, яке не перевищує задане число a;

б)  номера найменшого числа Фібоначчі, яке більше заданого числа a;

в)  суми всіх чисел Фібоначчі, які не перевищують 1000.

          3.29. Дана непорожня послідовність з натуральних чисел, за якою йде 0. Обчислити суму тих з них, порядкові номери яких - числа Фібоначчі.

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

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

б)  x_n=x_n-1+x_n-2+x_n-3+200,           x₁=x₂=x₃=-99,        n=4,5,...;

в)  x_n=x_n-1+x_n-3+100,                  x₁=x₂=x₃=-99,        n=4,5,...

          Розв`язок а) Оскільки послідовність x_n задана рекурентним співвідношенням другого порядку, то для обчислення довільного елементу послідовності потрібні три змінні.

          Нехай змінна u пробігає послідовність x_k, k=1,2,....Тоді, в якості умови завершення циклу будемо розглядати умову u>0. Її заперечення - це умоваu<=0  яка і розглядається як умова повторення циклу. Одержуємо алгоритм

          алгоритм Мінім_елемент це

                   змін  u,v,w:ціл;

          поч

                   u¬-99,v¬-99; {u=x₁, v=x₂}

                   поки u<=0 повт

                             w¬u+v+100;u¬v;v¬w

                   кц;

                   показати(u)

          ка.

          3.31. Скласти алгоритм, який з`ясовує, чи входить задана цифра до запису заданого натурального числа.

          3.32. Скласти алгоритм "обернення" (запису в оберненому порядку цифр) заданого натурального числа.

          Вказівка. Для побудови числа використати рекурентне спів­відношення y₀=0, y_i=y_i-1*10+a_i, де a_i - наступна цифра числа n при розгляді цифр справа наліво.

          3.33. Скласти алгоритм, який визначає потрібний спосіб розміну будь-якої суми грошей до 99 коп. за допомогою монет вартістю 1, 2, 3, 5, 10, 15, 20, 50 коп.

          3.34. Скласти алгоритми наближеного обчислення суми всіх доданків, абсолютна величина яких не менше e>0 :

а)  

б)  

в)  

г)  

д)  

е)  

ж)

з)  

і)   

к)  

л)  

м) 

н)  

о)  

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

          Розв`язок в) Рекурентне співвідношення для знаходження a_k має вигляд a₁=x, a_k+1=a_k*x²/(2*k*(2*k+1)), k=1,2,... Передбачивши захи­щене введення для завдання e, одержимо наступний алгоритм

          алгоритм Сінус_гіпербол  це

                   змін k:ціл;

                             x,y,z,a,eps:дійсн;

          поч

                   повт

                             взяти(x,eps)

                   до eps>0

                   кц;

                   k¬0;a¬x;z¬x*x;y¬0;

                   поки abs(a)>=eps повт

                             k¬k+1;y¬y+a;a¬a*z/(2*k*(2*k+1))

                   кц;

                   показати(y)

          ка.

          3.35. Маємо дійсні числа x,e (x¹0 ,e>0). Обчислити з точністю e нескінченну суму і вказати кількість врахованих доданків.

а)  ;           б) ;

в) ;          г) .

          3.36. Маємо ціле n>2. Скласти алгоритм для обчислення всіх простих чисел з діапазону  [2,n].

          Розв`язок. Нехай змінна m приймає послідовно значення цілих чисел з діапазону [2,n]. Тоді m буде простим числом , якщо воно не має дільників в діапазоні [2,]. Враховуючи цю обставину, складає­мо алгоритм

          алгоритм Прості_числа  це

                   змін k,n,m:нат;

                             p:бул;

          поч

                   повт

                             взяти(n);

                   до n>2

                   кц;

                   m¬2;

                   поки m<=n повт

                             p¬n;k¬2;

                             поки p&(k*k<=n) повт

                                      p¬n mod k<>0;

                                      якщо  p то k¬k+1 кр

                             кц;

                             якщо p то  показати(m,' просте') кр;

                             m¬m+1

                   кц

          ка.

          3.37. Скласти алгоритм друку всіх простих дільників заданого натурального числа.

          3.38. Скласти алгоритм, який визначає чи є задане натуральне число n досконалим, тобто рівним сумі всіх своїх (додатніх) дільників, крім самого цього числа (наприклад, число 6 - досконале: 6=1+2+3 ).

          Вказівка. Шукаємо суму S всіх дільників заданого числа n. Якщо S=n, то число, яке перевіряємо, є досконалим. Перша ідея полягає в знаходженні дільників числа n в діапазоні [1, n div 2]. У відповідності з другою ідеєю пошук ведеться тільки між 1 та  і якщо дільник знайдений, то до суми Sдодаються як дільник, так і частка.

          3.39. Дано натуральне число k . Скласти алгоритм одержання к-тої цифри послідовності

а)       110100100010000 ... , в якій виписані підряд степені 10;

б)      123456789101112 ... , в якій виписані підряд всі натуральні числа;

в)       149162536 ... , в якій виписані підряд квадрати всіх натуральних чисел;

г)       01123581321 ... , в якій виписані підряд всі числа Фібоначчі.

          3.40. Скласти алгоритм знаходження кореня рівняння tg x=x на відрізку [0,001;1,5] із заданою точністю e, використовуючи метод ділення відрізку навпіл.

          Розв`язок.

          алг корінь це

                   змін x,l,r,eps:дійсн;

          поч

                   повт

                             взяти (eps)

                   до eps>0;

                   l ¬0.001; r ¬1.5;

                   {лівий та правий кінці відрізка з коренем: tg(l)<l,tg(r)>r}

                   повт

                             x ¬(l+r)/2; {середина відрізка [l,r]}

                             якщо sin(x)/cos(x)<x то

                                      l ¬x {[l,r]¬[x,r]}

                             інакше

                                      r ¬x {[l,r]¬[l,x]}

                             кр

                   до l-r<eps

                   кц;

                   x ¬ (l+r)/2; {корінь - середина останнього відрізка [l,r]}

                   показати (х)

          ка.

          3.41. Знайти корінь рівняння  = 0, який міститься на відрізку [0,2], з заданою точністю e.

          Вказівка. Одним з методів розв`язування рівняння є метод хорд, який полягає в обчисленні елементів послідовності

                   

до виконання умови . В умовах нашої задачі а=0, b=2,  .