10.Берілген сан автоморфты екенін анықтау керек, яғни санның квадраты сол санмен аяқталады. Мысалы: 6 санының квадраты 36 – аяғында 6.
11.Алдындағы есептегі функцияны қолданып, A-дан B-ға дейін аралығынан барлық автоморфты сандарды табу керек.
12.Ең үлкен орта бөлгіш (ЕҮОБ) функциясын қолданып, бірнеше сандардың ЕҮОБ табу программасын құру керек. («Евклид алгоритмі» есебін қараңыз).
13.Клавиатурадан берілген төрт санның ең кіші жалпы еселігін есептейтін программа құру керек. (алдыңғы есептегі функция қолданылсын).
14.Төрт сан берілген. Берілген сандардың бірінші цифрларының ең үлкенін экранға шығару керек. Мысалы, егер a=25, b=730, c=127, d=1995, болса экранға 7 шығуы керек.
15.N натурал саны берілген. Жай сандардың айырмасы екіге тең болса, оларды егіз сандар дейді. Мына n, n+1, …, 2n сандарының арасында егіз сандар бар ма, соны анықтау қажет.
Рекурсивті программалау мысалдары
Рекурсиялық алгоритм – ол, құрылымы өз ішінен өзін шақыру түрінде ұйымдастырылған алгоритм. Осы әдіспен шығарылатын есептердің кейбір түрлерін қарастырайық.
Берілген формулировкасы айқын рекурсивті есептің мысалы:
Есеп: Натурал санының факториалын есептеу. N! есептеу үшін, (N-1)! мәнін білу керек және оны N-ге көбейту қажет, жәнеде 1!=1. Жалпы түрде жазылуы:
N!= |
ì1, |
N = 1 |
болѓанда |
|
í |
N *(N - 1)!, |
N > 1 |
болѓанда |
|
|
î |
|||
Факториалды есептеу үшін, оның мәнін есептейтін функцияны сипаттайық. Оның бір параметріне бұтін сан жіберіледі. Нәтиже де бүтін сан болады.
Function (factorial(n : integer) : longint;
Begin
If n = 1 then factorial := 1
else factorial := n* factorial (n-1);
End;
Функцияның шақырылу тізбегін n = 5 үшін қарастырайық. Бірінші рет функция негізгі программадан a:= factorial(5) операторымен шақырылады.
56
N ¹ 1 болғандықтан, else тармағынан кейінгі factorial функциясына n*factorial(n-1)–ң мәні, яғни 5* factorial(4) меншіктеледі.
4 – ке тең параметрімен функция екінші рет шақырылады.
Бұл процесс параметрдің мәні 1-ге тең болғанына дейін орындалады. Онда n = 1, сондықтан функцияның мәні factorial:=1 болады.
Сонымен, n = 1 рекурсияның аяқталу шарты.
Басқарылу шақырылу нүктесіне жіберіледі, яғни n=2 үшін: factorial:= factorial(n-1), демек factorial:= 2*1, сонымен factorial(2) = 2.
Шақырулардың рекурсивті тізбегімен «жоғары» көтеріле кері қайтамыз.
Сонымен, factorial (5) = 120, мәні алынып, а айнымалысына меншіктеледі.
Төменде осы рекурсивті процесстің орындалуының көрнекі схемасы бейнеленген:
57
1-ші шақыру (n=5) |
120 |
|
|
|
|
Function (factorial(n : |
: longint; |
Begin |
|
If n = 1 then factorial |
1 |
else factorial := n* factorial(n-1); |
|
End; |
|
2-ші шақыру (n=4) |
|
|
|
Function (factorial(n : |
longint; |
Begin |
|
If n = 1 then factorial |
|
else factorial := n* |
-1); |
End; |
|
3-ші шақыру (n=3) |
|
|
|
Function (factorial(n |
longint; |
Begin |
|
If n = 1 then |
|
else factorial := |
-1); |
End; |
|
4-ші шақыру (n=2) |
|
|
|
Function (factorial(n |
|
Begin |
|
If n = 1 then |
|
else factorial := |
1); |
End; |
|
5-ші шақыру (n=1)
Function (factorial(n : integer) : longint;
Begin
If n = 1 then factorial := 1
else factorial := n* factorial(n-1);
End;
Есептер
1. Клавиатурадан енгізілетін n және m оң сандары үшін, Аккерман функциясын мәндерін есептейтін рекурсивті функция жазу керек.
ì m + 1, |
|
егер |
N = |
0 |
|
ï |
A( n - |
1,1), |
егер |
n ¹ |
0, m = 0 |
A( n,m ) = í |
|||||
ï |
A( n - |
1, A( n, m - 1)), |
егер n > 0, m ³ 0 |
||
î |
|||||
2. Арифметикалық (геометриялық) прогрессияның бірінші N мүшесінің қосындысын табу керек.
58
3. Бірінші N Фибоначчи сандарын табу керек. Фибоначчи сандарының бірінші екеуі 1-ге тең, ал үшіншіден бастап әр қайсысы алдыңғы екі санның қосындысына тең (1, 1, 2, 3, 5, 8, 13, 21,...).
ì 1, |
егер n = 1 немесе n = 2 |
|
Ф( n )= í |
Ф( n - 1 )+ Ф( n - 2 ), |
егер n > 2 |
î |
||
Есептің қойылымынан рекурсия шығару мысалы:
Есеп: Натурал санын ондық жүйеден екілік жүйеге ауыстыру алгоритмін қарастырайық.
Шешімі. Берілген 23 санын екілік жүйіге аударайық. Ондық жүйедегі бүтін 23 санын, санау жүйесінің негізі 2 –ге сатылап бөлу процессін, бөлінді 2 – ден кіші болғанға дейін жүргіземіз.
Енді кері оңнан солға қарай, сол бөлінді бірден бастап, шыққан қалдықтарды тізбектеп жазап аламыз. Бұл 23 санының екілік жүйедегі
жазылуы болады: 2310 = 101112 |
|
|
|
||||
23 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
||
22 |
|
11 |
2 |
|
|
|
|
1 |
10 |
5 |
|
2 |
|
|
|
|
1 |
4 |
|
2 |
|
2 |
|
|
|
|
1 |
|
2 |
|
1 |
|
|
|
|
|
0 |
|
|
Сәйкес процедураны сипаттайық: Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2) Write(n mod 2);
End;
Процедураның шақырылу тізбегін 23 саны үшін қарастырайық. Бірінші рет функция негізгі программадан шақырылады.
Rec процедурасының соңғы 5-ші шақырылуынан кейін, экранға бірінші (1) цифры шығарылады.
Келесі (0) цифры экранға, 4-ші шақырылуынан кейін шығарылады, т.с.с.
Соңғы (1) цифры экранға – процедураның бірінші шақырылуынан кейін шығарылады.
Осы рекурсивті процесстің орындалуының көрнекі схемасы:
59
60
61
62
1-ші шақыру (n=23)
Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2)
Write(n mod 2);
End;
2-ші шақыру (n=11)
Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2)
Write(n mod 2);
End;
3-ші шақыру (n=5)
Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2)
Write(n mod 2);
End;
4-ші шақыру (n=2)
Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2)
Write(n mod 2);
End;
5-ші шақыру (n=1)
Procedure Rec (n : Integer);
Begin
If n > 1 then Rec (n div 2) Write(n mod 2);
End;
Тапсырма
Ондық жүйеден N санау жүйесіне аударатын процедураны жазу керек, 2 £ N £ 16 жағдайында (N – нің мәні клавиатурадан енгізіледі). Рекурсияның аяқталу шарты қандай болады?
Функцияның мінездемесін және қасиетін қолдану мысалы:
Есеп: Берілген натурал N ³ 1 саны үшін, 2a-1 £ N < 2a теңсіздігі орындалатын жалғыз a натурал санын анықтау керек.
Шешімі
a –ның мәні N –ге келесі түрде тәуелді екенін байқаймыз:
63
|
|
ì 1, |
егер, N = 1 |
|
a( N )= í |
егер, N > 1 |
|
|
|
î a( N div 2 ) + 1, |
|
Мысалмен қарастырайық, N=34 болсын. Осы сан үшін теңсіздік |
|||
орындалатын a санын табамыз: |
|
||
2а-1 £ 34 < 2а |
1 қосылады, және 34 div 2 –ке барады |
||
2а-1 £ 17 < 2а |
+1 |
|
|
2а-1 |
£ 8 < 2а |
+1 |
|
2а-1 |
£ 4 < 2а |
+1 |
|
2а-1 |
£ 2 < 2а |
+1 |
|
2а-1 |
£ 1 < 2а |
a = 1 болады |
|
Енді кері қайтып, алынған бірге алдындағы бірлерді қосамыз. Соныман 6 саны шығады.
Функцияны сипаттайық Function A(n : integer) : integer;
Begin
If N = 1 then A := 1
else A := A(N div 2) + 1;
End;
Тапсырма
Функцияның шақырылуларының схемасын құру керек.
64