- •1. ТУРБО ПАСКАЛЬ ПРОГРАММАЛАУ ОРТАСЫ
- •2.1. Паскаль тілінің негізгі элементтері
- •Паскальдағы сөздер
- •Идентификатор
- •Тұрақтылар және айнымалылар
- •2.2. Берілім типтері
- •Турбо Паскальдағы берілім типтерінің тізбесі
- •Логикалық тип
- •2.4. Амалдар, математикалық функциялар, өрнектер
- •2.5. Программаның құрылымы
- •2.6. Енгізу-шығару процедуралары
- •Экранға шығару форматтары
- •2.7. Қарапайым операторлар
- •2.8. Алгоритмдеудің негізгі құрылымдары
- •2.9. Тізбектеу құрылымды алгоритмдер
- •2.10. Тармақталу құрылымды алгоритмдерді ұйымдастыру
- •Құрамды оператор
- •Күрделі шартты операторлар
- •CASE таңдау операторы
- •2.11. Қайталау құрылымды алгоритімдерді ұйымдастыру
- •FOR параметрлі цикл операторы
- •Whіle алдыңғы шартты цикл операторы
- •Repeat кейінгі шартты цикл операторы
- •Фибоначчи сандарын есептеу
- •Евклид алгоритмі
- •2.12. Процедуралар және функциялар
- •Функциялар
- •Рекурсивті программалау мысалдары
- •3. ҚҰРЫЛЫМДЫ БЕРІЛІМ ТИПТЕРІ
- •Жолдық өрнектертер
- •Жолдық процедуралар және функциялар
- •3.2. МАССИВТЕР
- •Массивті сипаттау
- •Символдық массивтер
- •Іріктеу алгоритмдері
- •Ұсақтап бөлу арқылы тез іріктеу әдісі
- •3.3. ЖИЫНДАР
- •Жиындарға қолданылатын амалдар
- •3.4 ЖАЗБАЛАР
- •Типті сипаттау
- •Сатылы жазбалар
- •Файлдық типтер және айнымалылар
- •Сыртқы файлды программамен байланыстыру
- •Файлдан оқу
- •Файлға жазу
- •Файлды толықтыру
- •Мәтіндік файлдар
- •Қолданылған әдебиеттер
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