| Есепті шешу мысалдары
Тапсырма және жұмыстың орындалу тәртібі. Қарапайым арифметикалық есептеуді жүзеге асыратын программаны жазыңыз:
predicates
sred (integer, integer, real)
kvadr (integer, integer)
cub (integer, integer)
dmod (integer, integer, integer)
ddiv (integer, integer, real)
st (integer, integer, integer)
clauses
sred (A, B, D) :- D=(A+B)/2. /*орташа шамасын табу*/
kvadr (B, D) :- D=B*B. /* саннын квадратын есептеу*/
cub (B, D) :- D=B*B*B. /* кубты есептеу*/
dmod (A, B, D) :- D=A mod B./* бүтін санды бөлуден қалған қалдықты есептеу*/
ddiv (A, B, D) :- D=A div B. /* бүтінсандық бөлу*/
st (N, 0, 1) :- !. /*санды дәрежеге келтіру*/
st (N, P, R) :-
M=P-1,
st (N, M, Q),
R=N*Q.
Пролог тілінде программалаудың негізгі механизмдерінің біріне рекурсия жатады. Бұл механизмдерді оқып үйренуден бұрын, тізімдерді өңдеу туралы мәселені зерттеу қажет. Тізім – дегеніміз тәртіптелген элементтер жиынын (оның ішінде тізімнің өзі де элемент бола алады) білідіретін деректер құрылымы. Рекурсия тізімдік құрылымдарды өңдейтін табиғи әдіс. Пролог тілінде тізімдерді өңдеу үшін унификация процедуралы және рекурсияны пайдаланады. Тізімдер элементтері квадрат жақшаға [] алынып, бір-бірінен үтір арқылы бөлінеді. Пролог тіліндегі тізімдердің бірнеше мысалдарын келтірейік
[1, 2, 3, 4]
[[george, kate], [allen, amy], [don, pat]]
[tom, dick, harry, fred]
[[ ]
Тізімнің бірінші элементі оның құйрығынан (хвост) ~. – операторы арқылы бөлінеді. Тізім құйрығы деп бірінші элементті алып тастағандағы тізімді айтамыз. Мысалы [tom, dick, harry, fred] бірінші элемент tom, ал құйрығы — тізім [dick, harry, fred]. Унификация процедурасы және ~. – операторы көмегімен тізімді компоненталарға бөлуге болады.
• Егер тізім [tom, dick, harry, fred] шаблонына сәйкес келсе [Х ~ У], онда
Х = tom және Y = [dick, harry, fred]
• Егер тізім [tom, dick, harry, fred] шаблонына сәйкес келсе [Х, У~ Z] онда Х = tom,У = dick@ Z = [harry, fred]
• Егер тізім [ tom, dick, harry, f red] шаблонына сәйкес келсе у [Х, Z~W],TоX = tom, Y = dick,Z = harry,W = [fred].
• Егер тізім [~от, dick, harry, fred] шаблонына сәйкес келсе [W, Х, У,
Z~V], ондаW = tom,Х = dick,Y = harry,Z = fred,V =[].
Унификация процедурасын тізімді компоненталарға бөлумен бірге тізімдік құрылымды құру үшін пайдалануға болады. Мысалы егер Х = tom, Y = [dick] және L унификацияланса [Х ~ Y], онда L айнымалысы [ tom, dick] тізімімен байланыста болады. Тізімдегі бір-бірімен үтір арқылы бөлініп тік сызыққа дейін орналасқан термдер тізім элементтері болады да, ал тік сызықтан кейін орналасқан тізім құйрығы болады.
Тізімді рекурсивті түрде өңдеудің қарпайым мысалын қарастырайық. member предикаты көмегімен элементтің тізім элементіне жата ма соны тексеру қажет. Алдымен тізімде эелемент бар ма соны білетін предикатты анықтайық. member предикаты екі аргументтен тұрады: элемент және тізім. Ол егер берілген элемен тізімде бар болса "шын" мәнін қабылдайды.
Мысалы:
? member (а [а b с d, е] )
Yes
?- member(a, [1, 2, 3, 4]).
No
?- member(X, [а, b, c] ) .
Х=а
Х = b
X=c
Енді member предикатын рекурсивті түрде анықтау үшін, алдымен Х-тізімінің бірінші элементіме соны анықтайық.
member (X, [Х ~ Т] ) .
Бұл предикат Х мәні мен тізімдегі бірінші элемент ұқсас па, соны тексереді. Егер true болса, онда Х- тізімінің бөлігінде бар ма, сол тексеріледі. Бұл тексеру былайша өтеді.
member '(Х, [Y ~ Т] ): — member (Х, Т) .
Осылайша берілген элемент тізімде бар болуы PROLOG тіліндегі екі қатар предикаттар жолымен анықталады.
member (Х, [Х[Т] ) .
member (Х, [Y~ Т] ): — member(Х, Т) .
Бұл мысал тоқтау шарты рекурсивті шақыру алдында орындалатын, яғни алгоритм келесі болатын қадамның алдында орындалатын Пролог тілінедегі ішкі іздеу тәртібінің жұмыс істеу қалпын көрестеді. Предикаттарды керісінше шақырудың тәртібінде тоқта ушарты ешуақытта тексерілмеуі мүмкін. Мысалы member предикатының трассировкасын орындайық.
1: member(X, [Х~Т] ) .
2: member (Х, [Y ~ Т] ): — member (Х, Т) .
?- member(c, [а, b, с] ) .
call 1. fail, since сна
call 2. Х = с, Y = а, Т = [Ь, с], member(c, [Ь, с])?
call 1. fail, since с~Ь
call 2. Х = с, Y = b, Т = [с], member(c, [с])?
call 1. success, с = с
yes (to second call 2.) yes (to first call 2.)
yes
PROLOG тілінде прогараммалаудың жақсы стиліне анонимді айнымалыларды (anonymous variable) пайдаланады. Ол программалаушы мен интерпретаторға белгілі бір айнымалылар тек шаблонға сәйкес келуді тексеруді арналғанын көрсету үшін қызмет етеді. Яғни айнымалыларды өзара байланыстыру есептеу процесіне кірмейді. Сондықтан Х- тізімінің бірінші элементімен сәйкес келетінін тексеру үшін, әдетте member (Х, [Х/_] ) жазбасын пайдаланады. “-” – таңбасы сұратудың унификация процесіндегі тізім құйрығының маңыздылығына қарамастан, құйрық мазмұны ешқандай роль атқармайтынын көрсетеді. Рекурсивті тұжырымдарда анонимдік айнымалыларда пайдаланады. Оларды, егер тізім басы ешқандай роль атқармаған жағдайда, тізімде элемент бар ма , соны тексеру үшін қолданады.
member (Х, [X[]) .
member (Х, [ ~ Т] ): — member (X, Т) .
Тізімдер табиғаты мен рекурсивті басқаруды түсіну үшін, тізім элементтерін бір-бірден қатар бойынша жазу мысалын пайдалануға болады. Мысалы осындай жазба бойынша [а, b, с, d] тізім элементтерін жазу керек дейік. Ол үшін мына рекурсивті командаларды пайдалануға болады.
nitelist ( [ ] ) .
uritelist ( [Н ~ Т] ): — write (Н), nl, writelist (Т)
Бұл предикаттар тізім элементтерін әр жол қатарына бір-бірден жазады. nl –шығу ағынында жаңа жол қатарына өтуді білдіреді. Егер тізім элементтерін кері тәртіпте жазу қажет болса, онда рекурсивті предикат write командасының алдында болады. Онда тізім элементтері жазылмай тұрып-ақ тізім ең соңына дейін қаралып шығатынына кепілдік беруге болады. Содан соң тізімнің соңғы элементі жазылады да, тізімнің барлық алдыңғы элементтері үшін рекурсивті процедураны шақыру орындалады. Тізімді кері тәртіпте жазу былайша іске асады
reverse wr~tе1ist([ ]).
reverse writelist([H~T]) : :— reverse writelist(T), write(H), nl.
Осы предикаттардың жұмыс істеу тәртібін трассировка режимінде орындап тексеріп көруге болады.
Достарыңызбен бөлісу: |
