203
Жергілікті объектілер- феукция денесінде сипатталып сонда ғана
қоланылатын элементтер.
функцияның прототипі – (әдістемелік нұсқауды қараңыз)
Формальды аргумент – (әдістемелік нұсқауды қараңыз)
Нақты аргумент – (әдістемелік нұсқауды қараңыз)
Әдебиеттер:
[1-6],[13],[15].
204
Лабораториялық жұмыс №8
Тақырыбы: АЛГОРИТМДЕРДІ ҚҰРУДЫҢ РЕКУРСИЯЛЫҚ ӘДІСТЕРІ
Мақсаты: Студенттерді рекурсиялық функциялармен және рекурренттік
тізбектермен таныстыру.
Қажетті материалдар мен жабдықтар: ДК, лабораториялық жұмысты
орындауға арналған әдістемелік нұсқаулар.
Лабораториялық жұмыстың мазмұны және орындалу реті:
1. С/С ++ тілінде рекурсивті алгоритмдерді программалауға қатысты
әдістемелік нұсқау – матриалдарды алдын ала танысып меңгеру.
2. Ұсынылған мысалды орындау және талқылау.
3. Өзіндік жеке тапсырмалардың оқытушы ұсынған нұсқасын орындау.
4. Лабораториялық жұмыстың есебін (отчет) дайындап тапсыру.
Әдістемелік нұсқау:
Рекурренттік тізбек түсінігі математика курсынан белгілі. Мысалы, а
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
2
= 3, a
3
= 5, a
4
= 7, a
5
= 9, …
(1)
a
1
= 1, a
2
= 2, a
3
= 4, a
4
= 8, a
5
= 16, …
(1)
Келтірілген арифметикалық прогрессияның рекурренттік формуласы: a
i
= a
i
+ 2.
Келтірілген геометриялық прогрессияның рекурренттік формуласы: a
i
= 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 << ", ";
Достарыңызбен бөлісу: |
