Ііі. Есептің программасы



Pdf көрінісі
бет105/150
Дата21.05.2020
өлшемі1.13 Mb.
түріПрограмма
1   ...   101   102   103   104   105   106   107   108   ...   150
Әдістемелік нұсқау: 
 
Рекурренттік  тізбек  түсінігі  математика  курсынан  белгілі.  Мысалы,  а
1
,  ...,  а
k
 
тізбегінің  k  саны  белгілі  болсын.  Бұл  сандар  сандық  тізбектің  алғашқы  сандары 
болып табылады. Тізбектің келесі элементтері былай есептеледі: 
a
k+1
=F(a
1
, …, a
k
);  a
k+2
=F(a
2
, …, a
k+1
);  a
k+3
=F(a
3
, …, a
k+2
); …  
Мұндағы F дегеніміз k аргументтен тұратын функция.  
a
i
=F(a
i-1
,  a
i-2
,  …,  a
i-k
)  формуласы  рекуррентік  формула  деп  аталады.  Ал  k  өлшемі 
рекурсия тереңдігі деп аталады.  
 
Яғни,  рекурренттік  тізбек  дегеніміз  –  бұл  шексіз  сандар  тізбегі  және 
оның әр мүшесі алдыңғысы арқылы есептеледі, бастапқы k-ны санамағанда. 
Рекурренттік тізбек ретінде арифметикалық (1) және геометриялық (2) тізбектерді 
қарастыруға болады: 
a
1
 = 1,   a

= 3,   a

= 5,   a

= 7,   a

= 9, …   
 
 
 
 
(1) 
a
1
 = 1,   a

= 2,   a

= 4,   a

= 8,   a

= 16, …   
 
 
 
 
(1) 
Келтірілген арифметикалық прогрессияның рекурренттік формуласы:    a

= a

+ 2. 
Келтірілген геометриялық прогрессияның рекурренттік формуласы:     a

= 2 * a
i-1. 
Екі  жағдайда  да  рекурсия  тереңдігі  1-ге  тең  (мұндай  тәуелділікті  бір  қадамды 
рекурсия  деп  те  атайды).  Тармақталған  формулаға  келтірілген  жағдайда, 
арифметикалық прогрессия үшін: 
a
i
 = 







.
1
,
2
,
1
,
1
1
i
егер
a
i
егер
i
 
Геометриялық прогрессия үшін: 
a
i
 = 






.
1
,
*
2
,
1
,
1
1
i
егер
a
i
егер
i
 
 


205 
 
Есеп 1. Арифметикалық прогрессияның (1) n – ші элементін есептеңіз. 
 
#include  
 
int recurs_1( int n ) { 
  if ( n == 1 ) { 
    return 1; 
  } 
  return recurs_1( n - 1 ) + 2; 

 
void main() { 
  int number; 
  cout << "САн енгізіңіз: "; 
  cin  >> number; 
  cout << "Арифм. прогр. элементі = " << recurs_1( number ) << '\n'; 

Есеп  2.  Геометриялық  прогрессияның  (2)  алғашқы  n  элементін  қосындылаңыз 
(прогрессияның  алғашқы  n  мүшесінің  қосындысын  есептеу  формуласын 
пайдаланбаңыз). 
1 – ші шешу жолы сілтеме арқылы орындалған: 
 
#include  
 
int recurs_2( int n, int& s ) { 
  if ( n == 1 ) { 
    s = 1; 
    return 1; 
  } 
  int b = recurs_2( n - 1, s ) * 2; 
  s += b; 
  return b; 

void main() { 
  int number; 
  cout << "Санды енгізіңіз: "; 
  cin >> number; 
  cout << '\n'; 
  int summa; 
  cout << "Нәтижесі = " << recurs_2( number, summa ); 
  cout << " сумма = " << summa << '\n'; 

 
2 – ші шешу жолы глобалды айнымалыны қолдану арқылы орындалған: 
 


206 
 
#include  
 
int summa_2; 
 
int recurs_2_2( int n ) { 
  if ( n == 1 ) { 
    summa_2 = 1; 
    return 1; 
  } 
  int b = recurs_2_2( n - 1 ) * 2; 
  summa_2 += b; 
  return b; 

 
void main() { 
  int number; 
  cout << "Санды енгізіңіз: "; 
  cin >> number; 
  cout << '\n'; 
  summa_2 = 0; 
  cout << "Нәтижесі. = " << recurs_3_2( number ); 
  cout << " сумма = " << summa_2 << '\n'; 

 
Келесі сандық тізбек математикада Фибоначчи сандары ретінде танымал: 
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
Бұл  сандардың  ерекшелігі  үшінші  элементтен  бастап,  әр  сан  оның  алдындағы  екі 
санның  қосындысына  тең,  яғни  рекурренттік  тізбектің  тереңдігі  2-ге  тең  (екі 
қадамды рекурсия). Оны тармақталған түрде сипаттайық: 
a
i
 = 









.
2
,
,
2
,
1
,
1
2
1
i
егер
f
f
i
i
егер
i
i
 
Есеп 3. Алғашқы n Фибоначчи сандарын баспаға шығару. 
 
#include  
 
int recurs( int n, int& s ) { 
  if ( n == 2 ) { 
    s = 1; 
    cout << " 1, 1, "; 
    return 1; 
  } 
  int p; 
  s = recurs( n - 1, p ); 
  cout << s + p << ", "; 


207 
 
  return s + p; 

 
void main() { 
  int number, temp; 
  cout << "Введите число: "; 
  cin >> number; 
  cout << '\n'; 
  recurs( number, temp ); 

 
№8 лабораториялық жұмыстың тапсырмалары 
 
1.  Геометриялық прогрессияның (2) n – ші элементін есептеңіз. 
2.  Арифметикалық  прогрессияның  (1)  алғашқы  n  элементін  қосындылаңыз 
(прогрессияның  алғашқы  n  мүшесінің  қосындысын  есептеу  формуласын 
пайдаланбаңыз). 
3.  Алғашқы  n  Фибоначчи  сандарының  ішінен  жұп  сандардың  санын 
анықтаңыз. 
4.  Рекурренттік тізбек келесі түрде анықталған: 
a
i
 = 









.
0
,
1
*
,
0
,
1
1
i
åãåð
i
i
a
i
åãåð
i
 
Берілген нақты n үшін a

мәнін есептеңіз. 
5.  
a
i
 = 












.
1
,
1
,
1
,
0
,
1
1
2
i
егер
i
a
a
i
i
егер
i
i
 
1-20-ші элементтердің көбейтіндісін есептеңіз. 
6.  Рекурренттік әдісті пайдаланып, Горнер формуласы бойынша 10 дәрежелі 
көпмүшенің қосындысын есептеңіз. Мұндағы x – берілген нақты сан: 
 
10x
10
 + 9x
9
 + 8x
8
 + … + 2x
2
 + x = (( …((10x + 9)x + 8)x + … + 2)x + 1)x. 
7. Берілген нақты x пен натурал N үшін келесі тізбекті есептеңіз: 
 
x/(1 + x/(2 + x/(3 + x/( …/(N + )) … ). 
8.  
,
!
1
...,
,
!
3
1
,
!
2
1
,
1
N
 сандық қатарының 10
-5 
мәнінен асатын барлық мүшелерін 
есептеп, шығарыңыз. 
9. Берілген натурал N мен нақты x (x > 0) үшін келесі өрнектің мәнін есептеңіз: 
 
x
x
x



...
 
10. Факториалды есептеудің рекурсивті функциясын құрыңыз. 
11. Екі бүтін санның ең үлкен ортақ бөлгішін табу (ЕҮОБ) Евклид алгоритмін 
рекурсивті функцияның көмегімен программалаңыз. 
12. F(x)=x

функциясының есептелуін рекурсияны пайдаланып шығарыңыз. 


208 
 
13. F(x)=x
 
теңдеуін шешу үшін рекурсивті функция құрыңыз. Оның жұмысын 
cos(x) және sqrt(x+1) функциялары арқылы тексеріңіз. 
14. x нүктесіндегі n ретті Лежандр полиномының мәнін есептеу үшін рекрсивті 
функцияны құрыңыз. Лежандр полиномы келесі түрде анықталады: 
 
P
0
(x) = 1, 
 
P
1
(x) = x, 
 
P
n
(x) = ((2n-1)P
n-1
(x)-(n-1)P
n-2
(x))/n. 
15. Нүктемен аяқталған текст жолы берілген. Осы текстті кері ретпен экранға 
шығарыңыз. 
16. Берілген нақты x пен бүтін n бойынша x
n  
мәнін келесі формулаға сәйкес 
есептейтін рекусиялық функцияны құрыңыз: 
 
x















.
0
,
*
,
0
,
1
,
0
,
1
1
n
x
x
n
x
n
n
n
 
17. Нақты n және m сандары берілген. ЕҮОБ (n, m) = ЕҮОБ (m, r) (мұндағы r – 
n-ді m-ге бөлгендегі қалдық) қатынасына негізделген ең үлкен ортақ 
бөлгішті есептеу рекурсиялық функциясын пайдаланып, ЕҮОБ (n, m) 
табыңыз. 
 
Блиц- тест: 
1. 
Функция 
ешқандай 
мән 
қайтармаса 
қандай 
типпен 
сипатталады? 
A) Void; 
B) Int; 
C) Double; 
D) Char; 
E) Bool; 
 
2. Рекурсияның түрлері: 
A) Тіке, жанама. 
B) Тізбекті, тізбексіз. 
C) Статикалық, динамикалық. 
D) Терең, тайыз. 
E) Шексіз, шектеулі. 


Достарыңызбен бөлісу:
1   ...   101   102   103   104   105   106   107   108   ...   150




©engime.org 2020
әкімшілігінің қараңыз

    Басты бет