Бақылау мысалдары
Пример 1. Факториалды есептеу
factorial(X, _) :- X<0, ! ,fail.
factorial (0, 1) :- !.
factorial(N, Fact) :- N1=N-1, factorial(N1, Fact1), Fact=N*Fact1.
Мысал 2. Фибоначчи сандары:
F(1,1) :- !.
F(2,1) :- !.
F(I,R) :- I>2, I1=I-1, I2=I-2, F(I1,M), F(I2,N), R=N+M.
Жұмысқа тапсырма
1. Вариантқа сәйкес тапсырмаларды орындау.
2. Тест деректерін таңдау және есепті дайындау.
Тапсырма варианттары
Қайталанатын көбейту түрінде дәрежеге шығару.
Қайталанатын қосынды түрінде дәрежеге шығару.
Қалдықпен бөлудің (mod) рекурсивті анықтамасы.
Бүтіндей бөлудің (div) рекурсивті анықтамасы.
Евклида алгоритмі.
Аккермана функциясы
Ak(0,N) = N + 1
Ak(M,0) = Ak(M-1,1)
Ak(M,N) = Ak(M-1),Ak(M,N-1)
Екі санның ең үлкен ортақ бөлгіші.
Сандар қатарының ең үлкен ортақ бөлгіші.
Екі санның ең кіші ортақ еселігі.
Сандар қатарының ең кіші ортақ еселігі.
Бірлікті қосып/алу арқылы қосу және азайту.
Берілген саннан аспайтын барлық жай сандарды табу.
.
.
.Берілген санның Фибоначчи саны болатынын анықтау.
Берілген саннан аспайтын Фибоначчи сандарын табу.
Факториалды есептеу (жылдамдатылған алгоритм).
Арифметикалық прогрессияның, бірінші мүшесі – 1, ал айырмасы – 2 болатын n-ші мүшесін есептеу.
Геометриялық прогрессияның, бірінші мүшесі – 2, ал бөлгіші – 4 болатын n-ші мүшесін есептеу.
1 -ден n-ге дейінгі натурал сандардың қосындысы.
Үшке бөлінетін, барлық екі орынды сандардың қосындысы.
Не 5-ке, не 7-ге бөлінбейтін, барлық үш орынды сандардың қосындысы.
Қатардың алғашқы n мүшесінің қосындысын есептеу:
1 + 1/2 + 1/3 + ...
Қатардың алғашқы n мүшесінің қосындысын есептеу:
4 - 4/3 + 4/5 - 4/7 + 4/9 - ... + (-1)^(n-1) 4 / (2n - 1) + ...
Әрбір келесі мүшесі n-2–ші және n-3-ші мүшесінің қосындысына тең болатын, тізбектің n-ші мүшесін есептеуге арналған рекурсивті функцияны құру. Бірінші 3 мүшесі сәйкесінше 1, 2, 3 мәндеріне тең.
1 2 3 3 5 6 8 11
Әрбір жұп мүшесі алдындағы екі жұп элементтің қосындысына тең, ал тақ мүшесі алдындағы екі тақ элементтің қосындысына тең болатын тізбектің n-ші мүшесін есептеуге арналған рекурсивті функцияны құру керек. Алғашқы төрт мүшесі сәйкесінше 1, 2, 3, 4 мәндеріне тең.
1 2 3 4 4 6 7 10 11 16 18 ...
Әрбір келесі жұп мүшесі алдындағы екеуінің көбейтіндісіне тең, ал тақ мүшесі алдындағы екеуінің қосындысына тең болатын, тізбектің n-ші мүшесін есептеуге арналған рекурсивті функцияны құру керек. Алғашқы екі мүшесі сәйкесінше 1, 2 мәндеріне тең.
1 2 3 6 9 54 63 ...
Әрбір келесі мүшесі алдындағы екеуінің көбейтіндісіне тең, ал алғашқы екі мүшесі сәйкесінше 1 және 2 болатын, тізбектің n-ші мүшесін есептеуге арналған рекурсивті функцияны құру керек.
1 2 2 4 8 32 ...
Бірінші мүшесі 0-ге тең, екіншісі – 1, үшіншісі – 2, ал әрбір келесі мүшесі алдындағы үшеуінің қосындысына тең болатын, тізбектің n-ші мүшесін есептеуге арналған рекурсивті функцияны құру керек. .
0 1 2 3 6 11 ....
4.Зертханалық жұмыс№ 9. Пролог тілінде тізімдермен жұмыс
Жұмыстың мақсаты:
Пролог тілінде тізімдер типті деректер құрылымын жүзеге асыру және оларды өңдеу әдістерімен танысу.
Жұмысқа дайындалуға арналған тапсырма
"Тізімдер" тақырыбындағы лекцияларды қайталау.
Жұмысты орындау реті
1. Бақылау мысалдарын орындау.
2. Пролог тілінде, вариантқа сәйкес есептерді шешетін программа құру.
3. Орындалған жұмыстың есебін дайындау.
Есептің мазмұны
1. Пролог тіліндегі программаның бастапқы мәтіні.
2. Тест деректері мен программаның жұмысының нәтижесін теру.
3. Есепті шешу кезінде жіберілген қателердің тізімі мен талдауы.
4. Жұмыс бойынша қорытынды.
Негізгі түсініктер
Тізім – сандық емес программалауда кеңінен қолданылатын, деректердің қарапайым құрылымы . Тізім не бос болады, не екі бөлімнен тұрады: басы және аяғы. Тізімнің басы - атом, ал аяғы тізімнің өзі болып табылады. Прологтағы тізім – бұл екілік бұтақтың дербес жағдайы екенін ескерте кету керек.
Бақылау мысалы
Берліген саннан аспайтын барлық натурал сандардың тізімін құру керек.
create([],0).
create([X|T],X):-X>0, X1=X-1, create(T,X1).
Жұмысқа тапсырма
1. Тілдің мүмкіндіктерін қолданып,тізімдерді өңдеуге арналған функциялар жиынын жүзеге асыру керек:
Тізімге элемент қосу.
Тізімнен элементті жою.
Тізімдер конкатенациясы.
Тізімнің ұзындығын анықтау.
Екінші ретті тізімді ерекшелеу.
2.Құрылған функцияларды қолданып, вариантқа сәйкес қосымша есептерді шешу керек.
3. Тест деректерін таңдау және есепті дайындау.
Тапсырма варианттары
1. Келесі есептерді шешу керек:
а) тізімнің полиндром болатынын тексеру;
б) орналастыру әдісі бойынша тізімді реттеу;
в) тізімнің әрбір элементіне 1 қосу;
г) тізімнен оң және теріс сандар тізімін бөліп алу.
2. Келесі есептерді шешу керек:
а) тізімнің i-ші позициясына элемент қосу;
б) тізімнің барлық элементтерінің қосындысын есептеу;
в) тізімді инверттеу;
г) сандар жұбынан, сан осінде осы екі санның ортасында жататын натурал сандар тізімін құру.
3. Келесі есептерді шешу керек:
а) тізімнен барлық қайталанатын ішкі тізімдерді жою;
б) тізімдегі оң сандарды санау;
в) тізімнің оң элементтерінің қосындысы мен теріс элементтерінің көбейтіндісін есептеу;
г) тізімнің қайталанатын элементтерін санау.
4. Келесі есептерді шешу керек:
а) егер тізім элементі оң болса, 2-ге көбейту керек, ал теріс болса, 3-ке көбейту керек;
б) тізімді сұрыптау көмегімен кемуі бойынша реттеу керек;
в) үш тізімді біріктіру керек;
г) құрамында «а» әрпі бар тізімдерді тауып, оларды біріктіру керек.
5. Келесі есептерді шешу керек:
а) тізімінң i-ші позициясына элемент қосу;
б) тізімдегі бүтін сандардың қосындысын есептеу;
в) тізімнен оң және теріс сандар тізімін алу;
г) тізімді өсуі бойынша реттеу.
6. Келесі есептерді шешу керек:
а) сан осінде, берілген екі санның арасында жатқан натурал сандардан тізім құру;
б) тізімнің теріс, оң және нөлге тең емес элементтерінің санын анықтау;
в) тізімді инверттеу;
г) тізімді үш еселеу.
7. Келесі есептерді шешу керек:
а) тізімнен берілген ішкі тізімді жою;
б) тізімді кемуі бойынша реттеу;
в) символдардан тұратын тізімнің әрбір элементін, алфавиттің келесі символына ауыстыру;
г) тізімдегі қайталанатын элементтерді жою.
8. Келесі есептерді шешу керек:
а) тізімді өсуі бойынша реттеу;
б) тізімнің теріс, оң және нөлге тең емес элементтерінің санын анықтау;
в) тізімді инверттеу;
г) тізімнің әрбір элементінен 1-ді шегеру.
9. Келесі есептерді шешу керек:
а) тізімнен әріптер мен сандарды бөліп алу;
б) тізімнің симметриялығын тексеру;
в) тізімнің кіріктірілу деңгейінің санын анықтау;
г) тізімнің жұп элементтерінің қосындысын табу.
10. Келесі есептерді шешу керек:
а) барлық кіріктірілу деңгейінде тізімді инверттеу;
б) тізімде қатар тұрған барлық сандардың қосындысын табу;
в) тізімнің ұзындығын анықтау;
г) тізімнің тақ элементтерінің қосындысын табу.
11. Келесі есептерді шешу керек:
а) көрсетілген позицияға ішкі тізімді қосу керек;
б) тізімді инверттеу;
в) тізімнің оң элементтерінің мәндерін 2 еселеу және теріс элементтерінің мәндерін 3 еселеу;
г) тізімнің 10-нан үлкен элементтерінің санын анықтау.
12. Келесі есептерді шешу керек:
а) көрсетілген тереңдіктегі ішкі тізімді жою;
б) компоненттері берілген аралыққа тиісті ішкі тізімді шығару;
в) тізімнен 2 және 3 сандарына бөлінетін элементтерді бөліп алу;
г) тізімді симметриялыққа тексеру.
13. Келесі есептерді шешу керек:
а) тізімді инверттеу;
б) тізімнің оң элементтерінің қосындысын есептеу;
в) тізімнің оң, теріс және нөлге тең емес элементтерін бөліп алу;
г) 3 тізімді біріктіру..
14. Келесі есептерді шешу керек:
а) тізімді орналастыру әдісімен өсуі бойынша реттеу;
б) ішкі тізімнің тізімге кіруін анқытау;
в) тізімнің орта мәнін есептеу;
г) натурал сандардан тұратын тізімді екі ішкі тізімге бөлу, бірінші тізімге көрсетілген аралықтағы сандарды кіргізу, ал екіншісіне – қалғандарын кіргізу.
5.
6.Зертханалық жұмыс № 10. Бинарлық бұтақтар
Жұмыстың мақсаты
1. Деректердің рекурсивті типтерін сипаттауды үйрену.
2. Құрылымды бұтақ түрінцде ұсыну дағдыларын қалыптастыру.
Жұмысқа дайындалуға арнлған тапсырмалар
«Рекурсивті деректер типі. Бұтақтар» тақырыбы бойынша лекция материалдарын қайталау.
Жұмыстың орындалу реті
1. Бақылау мысалдарын орындау.
2. Пролог тілінде, вариантқа сәйкес есептерді шешетін программа құру.
3. Орындалған жұмыстың есебін дайындау.
Есептің мазмұны
1. Пролог тіліндегі программаның бастапқы мәтіні.
2. Тест деректері мен программаның жұмысының нәтижесін теру.
3. Есепті шешу кезінде жіберілген қателердің тізімі мен талдауы.
4. Жұмыс бойынша қорытынды.
Негізгі түсініктер
Деректер құрылымнда рекурсияның болуын қабылдайтын деректер типі рекурсивті болып табылады.
Рекурсивті деректер типіне бинарлық бұтақтар мысал бола алады. Бинарлық бұтақтар не бос болады, не келесі үш бөлімнен тұрады:
түбір;
сол жақ ішкі бұтақ;
оң жақ ішкі бұтақ.
Мұндағы сол жақтағы және оң жақтағы ішкі бұтақтар өздері бинарлық бұтақтар болып табылады. Сонымен, бинарлық бұтақтың рекурсивтілігі оның анықтамасының өзінде көрініп тұр.
Бинарлық бұтақ реттелген деп есептеледі, егер оның сол жақ ішкі бұтақтарының барлық төбелері түбірден кіші болса, ал оң жақ ішкі бұтақтарының барлық төбелері түбірден үлкен болса және екі ішкі бұтақтары да реттелген болса. Мұндай бұтақ бинарлық анықтамалық деп аталады. Реттеудің артықшылығы мынада, бинарлық анықтамалықтан қандай-да бір объектіні табу үшін, бір ғана ішкі бұтақты қарап шығу жеткілікті.
Бинарлық бұтақты құруға және модификациялауға арналған предикатттарды сипаттаймыз. Бинарлық бұтақ келесі функтор көмегімен беріледі.
tree(K, LeftT, RightT),
где К – элемент, находящийся в вершине; LeftT и RightT – левое и правое поддерево соответственно.
create_tree(A, tree(A, empty, empty)). % создание дерева
insert_left(X, tree(A, _, B), tree(A, X, B)). % включение элемента данных A, как левого поддерева B
insert_right(X, tree(A, B, _), tree(A, B, X)). % включение элемента данных A, как правого поддерева B
Для обхода бинарного дерева «сверху вниз» опишем предикат:
up_to_down(tree(X, LTr, RTr), Xs) :- up_to_down(Ltr, Ls), up_to_down(RTr, Rs), append([X|Ls], Rs, Xs).
up_to_down(empty, []).
append – это процедура append(LeftList, RightList, ListRes), где ListRes является результатом слияния списков LeftList, RightList.
Аналогичным образом можно описать процедуру обхода дерева «снизу вверх», «слева направо».