Пәндердің оқу-әдістемелік кешенінің тізімдемесі
Тақырып №12: Пролог жүйесіндегі жиындар мен ағаштар. Жиындар мен ағаштарға қолданылатын амалдар
жүктеу/скачать 2.35 Mb.
|
- Бұл бет үшін навигация:
- Бинарлы ағаштар, екілік анықтамалық және олармен жұмыс ұйымдастыру
| Тақырып №12: Пролог жүйесіндегі жиындар мен ағаштар. Жиындар мен ағаштарға қолданылатын амалдар.
Пролог жүйесінде берілгендер қорының құрылымы жиындарға ұқсас бола алмайды. Сондықтан стандартты домендерге сүйене отырып, бұл түсінік қалыптасады. Базалық домен ретінде стандартты тізімдер доменін. ал жиын ретінде қарапайым тізімді алуға болады. Бұл тізімде предикаттарды қолдануға болады. Қайталанып жазылған тізімдер delete all предикаты арқылы өшіріледі. Предикат екі аргументті болады: енгізілген тізімді (яғни қайталанбалы элементті) және нәтиже шығарушы (яғни қайталанбалы кіріс элементтерін өшіру). Предикат рекурсия көмегімен құрылады. Басқа программалау тілінде қайталанбайтын әрекеттер цикл көмегімен орындалса, Пролог тілінде қайтарымы бар іздеу процедурасы (Откад) рекурсия арқылы жүзеге асырылады. Откад программаға қойылған бір сұраққа көптеген шешімдер алуға мүмкіндік береді. Рекурсияны анықтау үшін жауап іздеу процесінде предикаттың өзін қолданады. Рекурсия базасында тізімдегі элементтер қайталанбайды. Рекурсия қадамы ережелердің орындалуына мүмкіндік береді, яғни тізімдегі элементтер өшіріледі және барлық тізімдер жиынға келтіріледі. Алынған нәтижеге байланысты тізімдер соңы бірінші элементтің басы ретінде алынады. Алынған талқыламаны кодтап жазсақ төмендегідей түрге келеді: list_set([],[]). /* бос тізім алыннып жатқан тізімге жатады*/ list_set ([H|T],[H|T1]) :– delete_all(H,T,T2), /* T2 – H тізімінің бірінші элементінің жойылуы T */ list_set (T2,T1). /* T1 — T2 тізіміндегі қайталанып жазылған элементтердің жойылуы*/ Мысалы, бұл предикат мына түрдегі тізімге қолданылса {1, 2, 1, 2, 3, 4, 1}, онда нәтижесінде тізім мына түрге келеді: {1, 2, 3}. List Set предикатында жазылған кері байланысты жиыннан тізімге айналдырудың ешбір қажетті болмайды. Себебі, алынған жиын тізім болып келеді. Теориялық жиын операциясында біз бірігу, қиылысу және жиынның түрленуі, яғни жиын элементтерімен танысамыз. Теориялық жиын операциясында бұл предикаттарды қарапайым тізіммен жұмыс істеу кезінде қолдануға болатын еді, бірақ нәтижесінде бұл тізімде кейбір элементтер бірнеше рет қайталанар еді. List Set предикаты арқылы теориялық жиын операциясында алынған тізімді жиынға айналдыруға болады, бірақ ол қолайсыз болып табылады. Мұндағы мақсат - теориялық жиын операциясынан әрбір элементті жұмыс нәтижесінде жиын шығатындай ету. Member 3 предикаты операция барысында жиынға тиісті элемент ретінде алынады, яғни Х элементі А жиынына тиісті болады. Бұл математикада былай бейнеленеді: x A. Ол жиындардың бірігуі үшін Length предикаты қолданылады, яғни еске түсірсек аяқталушы жиынға қуат жиын ішіндегі элементтер санын айтады. Мысалы ретінде, екі жиынның бірігу операциясын алайық. Екі жиынның бірігуі дегеніміз - жиын элементінің бірінші жынға немесе екінші жиынға тиісті екені айтылады. Яғни бірігу жиынының А және В жиыны былай белгіленеді: A B, ал математикалық жолмен мына түрге келеді: A B={x | x A немесе x B}. Жиындардың бірігуін штрихпен белгілейді. 1 – сурет. А және В жиындарын біріктіру. Бұл операция предикатында үш параметр болуы керек: екеуі – жиын, яғни біріктіруші. Ал үшінші параметр екі алғашқы аргументтің бірігу нәтижесі. Үшінші аргумент бірінші және үшінші жиын элементтеріне тәуелді болып келеді. Ал егер Conc предикатын қолдану арқылы жазылса, онда мәндері бірнеше рет қайталанып тәуелсіз болады. Оны келесі түрден көре аламыз: union([ ],S2,S2). /* S2 жиынымен біріккен бос жиын S2 жиыны болып саналады. */ union([H|T],S2,S):– member3(H,S2), /* H бірінші жиын басы екінші S2 жиынына тиісті болса, */ !, union(T,S2,S). /*нәтижесінде S бірігуі T жиынына бірігіп S2 жиынына қосылады */ union([H |T],S2,[H|S]):– union(T,S2,S). /* керісінше қарастырсақ Н бірінші жиын басы Тжиыны мен S2 жиынынан алынады */ Егер [1, 2, 3, 4] жиынын [3, 4, 5] жиындарымен біріктірілсе, онда нәтижесінде [1, 2, 3, 4, 5] жиындары шығады. Мысалы, екі жиынның қиылысуын қарастырайық. Еске сала кететін бір жай, яғни екі жиындардың қиылысуы - бұл элементтердің бір уақытта бірінші жиынға да, екінші жиынға тиісті жиындар аталады. А және В жиындарының қиылысуы былай бейнеленеді: A B,ал математикалық түрде мына түрге келеді: A B={x|x A и x B}. Төмендегі суретте жиынның құрылысы бейнеленген. А және В жиындарының қиылысуы штрихпен б елгіленеді. 2 – сурет. А және В жиындарының қиылысуы. Бұл операцияда үш параметр болады. Бірінші екеуі – кіріс жиыны, ал үшіншісі – екі аргументтің нәтижесі. Рекурсия базасы бос жиынның басқа жиынмен қиылысуы бос жиын беп аталады. Рекурсия қадамы сонда бірігу жағдайында екі жағдайға бөлінеді. Бірінші жағдайда, бірінші жиын элементінің басы екінші жиынмен қиылысады. Екінші жағдайда, бірінші жиын элементтері екінші жиын элементтеріне тиісті болмайды. Мұндай жағдай төмендегі предикаттар арқылы кодталады: intersection([],_,[]). /* кез келген жиынның бос жиынмен қиылысу нәтижесінен бос жиын шығады */ intersection([H|T1],S2,[H|T]):– member3(H,S2), /* Егер H бірінші жиынның басы S2 жиынының басына тиісті болса */ !, intersection(T1,S2,T). /* нәтижесінде бірінші Н жиынының аяғынан және Т1 және S2 жиындарымен қиылысқан жиын алынады */ intersection([_|T],S2,S):– intersection(T,S2,S). /* кері жағдайда S2 және Т жиындарының нәтижесінен алынған жиын S нәтижелік жиын болып табылады */ Егер [1, 2, 3, 4] жиындарын [3, 4, 5] жиындарымен қиылыстырса, онда нәтижесінде [3, 4] жиыны пайда болады. Келесі операция екі жиынның айырымы операциясы. Мұнда А және В жиындарын былай жазуға болады: А– В және А/В, ал математикалық түрде былай бейнеленеді A\B={x|x A и х B}. Төмендегі суретте А және В жиын айрымы штрихпен бейнеленеді. А және В жиынының айырымы В және А жиындарының айырымы Мұндай жағдайда жиындар реттеліп орналасуы керек Аргументі үш жағдайда қарастырылады: бірінші жағдайда, бөліп алатын жиын; екінші жағдайда бөліп алатын жиын; үшінші жағдайда, екінші аргументті біріншісіне көбейту. Үшінші параметр элементтері бірінші жиынға және екінші жиынға тиісті болмауы тиіс. Яғни мұндай жағдай төмендегідей бейнеленед: minus([],_,[]). /* кез келген жиынды бос жиыннан алғанымызда бос жиын шығады. */ minus([H|T],S2,S):– member3(H,S2), /* егер бірінші Н жиынының элементі S2 жиынына тиісті болса,*/ !, minus(T,S2,S). /* сонда нәтижелік S жиыны T бірінші жиынның аяғы және S2 екінші жиынның басынан тұрады*/ minus([H|T],S2,[H|S]):– minus(T,S2,S). /* кері жағдайда, нәтижелі жиын бірінші элементтің бірінші жиыны Н – тан және аяғы бірінші жиыннан алынған Т екінші жиын S2- ден алынады */ Екі жиынның қиылысуынан айырымдар арқылы жасауға болады. Математикада А және В жиындары мына түрде бейнеленеді: A B=A\(A\B). Сәйкес предикаттарын қолданып, алынған айырымдардың қиылысуын арқылы нақтылауға болады. Мұндай жағдай intersection предикатты арқылы кодталады: intersection2 (A,B,S):– minus(A,B,A_B), /*A_B=A\B */ minus(A,A_B,S). /* S = A\A_B = A\(A\B) */ Жиындардың тағы бір әдісі толықтырғыш әдісі. Толықтырғыш жиын дегеніміз - әдетте шығыс элементтері құрамына енбейтін жиындарды атайды. Толықтырғыш А жиындарын деп белгілейді. Математикалық тұрғыдан ол мына түрде сипатталады: ={x|x A}.Толықтырғыш жиындар ретінде универсал жиындарын алуға болады. Мысалы жиындар ретінде натурал сандар, орыс әріп жиындары, символдар жиындары, арифметикалық әрекеттерді және т.б. алуға болады. Универсалды жиындарды анықтау үшін ({0,1,2,3,4,5,6,7,8,9}) сандары алынады. Осы универсал жиындарды толықтыру үшін, бұл мәселеге математикалық әдісті қолдануға болады, яғни =U/A, мұнда U символы универсалды жиынды білдіреді. Осы айтылғандарды Прологта тілімен төмендегідей кодтауға болады: supp(A,D):– U=[0,1,2,3,4,5,6,7,8,9], minus(U,A,D). /* D — бұл толықтырғыш, яғни U универсалды жиыны мен А жиынынан құрылған*/ [1,2,3,4] толықтыру жиыны [0,5,6,7,8,9] – ға тең. Толықтыру негізін біріктірулер арқылы толықтыруды және қиылысуды немесе керісінше қиылысу операциясын біріктіру және толықтыру арқылы алуға болады. Мұнда Морган заңы қолданылады: (A B=A B и A B=A B). Бұл қатынас Прологта төмендегідей жазылады: unionI(A,B,AB):– supp(A,A_), /* A_ — бұл A жиынының толықтырғышы*/ Supp (B, B_), /* B_ — бұл В жиынының толықтырғышы */ Intersection (A_, B_, A_B), /* A_B — бұл A_ және B_ жиынының қиылысуы */ Supp (A_B, AB). /* AB — бұл A_B жиындарының толықтырғышы */ Intersection (A, B, AB):– supp (A,A_), /* A_ —бұл A жиынының толықтырғышы*/ supp(B,B_), /* B_ — бұл B жиынының толықтырғышы */ union(A_,B_,A_B), /* A_B — бұл A_ және B_ жиындарының бірігуі */ supp(A_B,AB). /* AB — бұл A_B жиындарының толықтырғышы */ Келтірілген мысалдарға қарай union және intersection предикаттарының жұмысын байқадық. Бинарлы ағаштар, екілік анықтамалық және олармен жұмыс ұйымдастыру Әдетте графалар дегеніміз - екі жиынды, яғни төбелер жиыны мен доға жиынын атайды. Графалар екі түрге бөлінеді: хабарлы және хабарсыз графалар. Әр доғаларының өзінің бағыты болады. Графикалық түрде әдетте графалар төбелерін нүктелермен, ал олардың арасындағы байланыстарын сызықтармен бейнелейді, яғни төбелері нүктелер арқылы қосылады. Жол дегеніміз - төбелердің бір ізділігін айтады, яғни олар доғалармен қиылысады. Жолдар бағыты әр доға бағыттарымен сәйкес келуі керек. Цикл деп - басы мен аяғы сәйкес келетін жолды атайды. Графиктегі доғамен қосылған екі төбені әкесі және баласы немесе басыңқы және бағынышты төбелер деп аталады. Егер граф циклы болмаса, онда ол ешкімнің баласына жатпайтын әйтеуір бір төбенің болатыны белгілі. Осындай төбені түбірлі деп аталады. Егер бір төбеден келесі төбеге өтсек, онда оның біріншісін - баба, ал екіншісін ұрпақ деп атайды. Ағаш деп - бір түбірлі төбе графын атайды. Яғни мұнда қалған төбелер бір әкеден және барлық төбелер түбірлі төбе ұрпақтары болады. Ағаш жапырағы деп - балалары жоқ төбелерді атайды. Ағаштың ұзындығы дегеніміз - жапыраққа дейінгі жолды атайды. Бинарлы ағаштарды әдетте рекурсивті анықтауға жеңіл болады: ағашта дым жоқ немесе тамырдан тұрады, сондай –ақ онды - солды ағаштың қол астында болады. Ағаш төбелерінде кез келген ақпаратты сақтауға болады. Мысалы ретінде қарапайым бүтін сандарды қарастыруға болады. Анықтамалықта бейнеленгендей альтернативті домендер түрі төмендегідей болады: DOMAINS tree=empty;tr(i,tree,tree) /* ағаш бос не тамырдан (яғни бүтін сан), оң және сол бұтақтардан тұрады. */ Ескеретін жағдай, empty идентификаторы Пролог тілінің сөздер қорына жатпайды. Бұл сөз орнына бос ағаш үшін кез келген белгілеу алуға болады. Мысалы, ағашты белгілеу үшін төбелері болатын nil идентификаторын қолдануға болады. Бұл домен атына идентификаторлар қолдануға болады. Келесі түрге келтіруге болады: tr(2,tr(7,empty, empty),tr(3,tree(4,empty,empty), tr(1,empty,empty))). Енді бинарлы ағаштар үшін предикаттардың қолданылуын қарастырайық. Предикат екі аргументті болады. Бірінші аргумент ретінде шығыс мәні алынады, ал екіншісіне ағаш алынады, яғни мұнда берілген мәнді табылуы шарт. Кейбір мәндердің берілген ағашқа тиісті екенін ескерсек, Пролог тілінде төмендегідей бейнеленеді: tree_member(X,tr(X,_,_)):-!. /* X – ағаш тамыры болып табылады */ tree_member(X,tr(_,L,_)):- tree_member(X,L),!. /* X сол жақ бұтаққа жатады */ tree_member(X,tr(_,_,R)):- tree_member(X,R). /* X оң жақ бұтаққа жатады */ Ағаштағы кіріс мәндерінің біреуін екіншісімен алмастырылатындай предикат қарастырайық. Предикат 4 аргументті болады, яғни үшеуі орындарын алмастыратын мәндер, ал төртіншісі шығыс аргументі ағаш болып табылады. Бос ағаштан бос ағаш алады. Рекурсия тамырындағы ауыстырылатын мәнге байланысты Пролог тілінде төмендегідей бейнеленеді: tree_replace(_,_,empty,empty). /*бос ағаш бос ағаш болып қалады*/ tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):- /* тамырда ауыстырғыш мән X болады */ !,tree_replace(X,Y,L,L1), /* L1 - L ағашын ауыстыру нәтижесі,барлық кірісті қамтиды X - Y */ tree_replace(X,Y,R,R1). /* R1 – R ағашын ауыстыру нәтижесі, барлық кірісті қамтиды X - Y */ tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):- /* тамырда ауыстырғыш мән X болмайды */ tree_replace(X,Y,L,L1), /* L1 - L ағашын ауыстыру нәтижесі,барлық кірісті қамтиды X- Y */ tree_replace(X,Y,R,R1). /* R1 – R ағашын ауыстыру нәтижесі, барлық кірісті қамтиды X - Y */ Ағаш төбелерінің барлық санын шығаратын предикат жазамыз.Ол екі параметрлі болады. Біріншісі ағаштар параметр, ал екіншісі ағаштағы төбелер саны: әдеттегідей рекурссия қолданылады. Базисі бос ағаштардың төбелер саны 0-ге тең болады.Рекурссия қадамы: ағаштардың төбелерінің санын білу үшін оның оң жағындағы және сол жағындағы төбелерінің санын білу керек. Төмендегідей предикаттарды қолданымыз: Tree_length (empty,0). /*бос ағашта шыңы жоқ*/ Tree_length (tr(_0,R),N): - Tree_length (L,N1), /* N1 – сол бұтақ шыңы саны*/ Tree_length (R,N2), /* N2 – оң жақ бұтақ саны*/ N = N1+ N2 + 1 /*ағаштың бүтын бөлігін есептеу N1 және N2 қосылғышынан есептелінеді*/ Ал ағаштағы бұтақтардың жапырақтарының санын есептеу үшін төмендегідей предикаттарды қолданамыз: tree_leaves(empty,0). /* бос ағашта жапырақ жоқ */ tree_leaves(tr(_,empty,empty),1):-!. /*бір тамырлы ағашта бір жапырақ */ tree_leaves(tr(_,L,R),N):- tree_leaves(L,N1), /* N1 – сол жақ бұтақ жапырақтары саны */ tree_leaves(R,N2), /* N2 – оң жақ бұтақ жапырақтар саны */ N=N1+N2. Ағаш төбелерінде орналасқан сандар суммасын табатын предикатты құрастырайық. Ол екі аргументті болады. Біріншісі шығыс тізімді, ал екіншісі ағаш төбелерінің сандарының суммасы болып табылады. Пролог тілінде төмендегідей предикаттарды қолдану арқылы жазылады: tree_sum (empty,0). /* бос ағаштың шыңы болмайды */ tree_sum(tr(X,L,R),N):- tree_sum (L,N1), /* N1 – сол жақ бұтақтың элементтер суммасы */ tree_sum (R,N2), /* N2 – оң жақ бұтақтың элементтер суммасы */ N=N1+N2+X. /* N1, N2реттеу және тамырлар мәнін анықтау */ Ағаштың ұзындығын табуға мүмкіндік беретін ағаш предикатын ойластырайық. Предикат екі параметрлі болады. Біріншісі ағаш, екіншісі ағаш ұзындығы. Базистің рекурсиясынан бос ағаш биіктігі нольге тең. Рекурсия қадамы ағаштардың биіктігін санау кездегі максимум мен минимум деңгейін есептеу керек. Пролог тілінен төмендегідей кодтар арқылы жазылады: tree_height(empty,0). /* бос ағаш ұзындығы 0 – ге тең */ tree_height(tr(_,L,R),D) :- tree_height(L,D1), /* D1 – сол жақ бұтақтарының ұзындығы */ tree_height(R,D2), /* D2 – оң жақ бұтақтарының ұзындығы */ max(D1,D2,D_M), /* D_M – оң және сол жақ бұтақтарының максимумы */ D=D_M+1. /* D – ағаштар ұзындығы D_M мәнін бірге арттырғаннан есептелінеді*/ Бинарлы ағаштардың ерекше бір түрі екілік анықтамалық болып табылады. Екілік анықтамалық мәндері, яғни сол жақ бұтақтарына тиісті мәндер тамырда орналасқан мәндерден кіші болады, ал биікте орналасқан оң бұтақтағы мәндер тамырдағы мәндерден үлкен болады. Мұндай ағаштар солдан оңға ретке келтіру деп аталады. Tree - member предикатының екілік анықтамалыққа жататындығы жөнінде мысал келтірейік. Бұл предикат модификациясы төмендегідей болады: tree_member2(X,tr(X,_,_)):-!. /* X – ағаш тамыры*/ tree_member2(X,tr(K,L,_)):- X /* X – сол жақ бұтаққа жатады */ tree_member2(X,tr(K,_,R)):- X>K,!, tree_member2(X,R). /* X – оң жақ бұтаққа жатады */ Екілік анықтамалыққа жаңа мән беруге мүмкіндік беретін предикат құрайық, яғни нәтижесінде екілік ағаш құрылуы тиіс. Предикат үш аргументті болады. Бірінші аргумент қосылғыштың мәні болады, екінші аргумент берілген мәнді қосатын ағаш, ал үшінші аргумент бірінші аргументінің екінші аргументке қойылу нәтижесі болып табылады. Шешімі рекурсивті болады. Біздің рекурсиямыз екі базистен және екі ережеден құралады. Бірінші базисіміздің негізі мынада: егер кез келген мәнді бос ағашқа қойсақ, онда нәтижесінде оң және сол жақтағы бұтақтары ретінде бос және қосылатын мәндері жазылатын ағаштар алынады. Екінші базис мәні: егер қойлатын мән тамырдағы мәнге сәйкес келсе, онда нәтиже шығатын ағаштан ерекше болмайды. Пролог тілінде төмендегідей бейнеленеді: tree_insert(X,empty,tr(X,empty,empty)). tree_insert(X,tr(X,L,R),tr(X,L,R)):-!. tree_insert(X,tr(K,L,R),tr(K,L1,R)):- X tree_insert(X,tr(K,L,R),tr(K,L,R1)):- tree_insert(X,R,R1). Берілген мысалымыздағы екі предикаттың ерекшелігі мынада: біріншіден биіктігіндей жаңа мәндері ағаштың жаңа жапырағының мәндері негізіне алынады. Екіншіден егер қосылатын мән біздің екілік анықтамалығымыздың құрамында болса, онда ол ағаш құрамына ешқандай мән қосылмай өз қалпында қалады. Tree - Insert предикатын қолданған кездегі ағаш түрі төмендегідей болады: tree_gen(0,empty):-!. tree_gen (N,T):- random(100,X), N1= N-1, tree_gen (N1,T1), tree_insert(X,T1,T Жиындарды тізім түрінде де кездеседі. Бірақ та бұл жиындардың элементтер саны өте үлкен болғандықтан жиындарды тізімге айналдыру тиімсіз әдіс болып табылады. Мысал ретінде мына мысалды қарастырайық. Тізім ретінде L – тізімін алайық. Мұндағы бейнеленген жиын алғашқы 1024 натурал сандардан құралсын. Сонда сұранысқа жауап ретінде: ? – тиісті (3000, b). Сонда Прологқа мұндай санның жоқ екенін көрсету үшін 1024 санның барлығын тексеру керек болады. Жиындарды бинарлы ағаш ретінде қарастыру жақсы нәтиже береді. Мұндай жағдайда бинарлы ағаштың сол жақ бұтағындағы әрбір элементі тамырына қарағанда кіші болуы керек. Ал оң жақ бұтағының әрбір элементі тамырдан үлкен болуы тиіс. Барлық жиынды бинарлы ағаш ретінде қарастырғандықтан бұл ж 1 – сурет. Ретке келтірілген бинарлы ағаш. 3 – сурет. Тізім түрі ағдай барлық бұтақтарға қатысты болады. 2 – сурет. Ретке келтірілмеген бинарлы ағаш Бинарлы ағаштардың сол жақ, оң жақ және тамырлары рекурсивті болып табылады. Сол жақ және оң жақ бұтақтарының өздері бинарлы ағаш бөлігі болып табылады. Бұл ағаш түрлерін терм түрімен де көрсетуге болады. бд(Лд, К, Пд), мұнда Лд – сол жақ бұтақ, К – тамыр, ал Пд – оң жақ бұтақ болып табылады. «Дл» бос бинар ағашын белгілейді, мұнда nil атомын қолдана аламыз. бд(бд(nil, d, nil), b, бд(nil, е, nil)) оң жақ бұтақтар бд(nil,с, nil) түгелімен төмендегідей жазылады. бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)). Жиынға қатысты моделдеу әдісі де қолданылады. Жиынды бинарлы ағаш түріне келтіріп те моделдеуге болады. Мұндай жағдайда @ < операторлары қолданылады. Бұл операторлар «кіші немесе» және «үлкен немесе» дегенді білдіреді. Егер ағаш құрамында берілген бірінші параметрдегідей ұзындықтарымен сәйкес келсе, оны бірнеше тәсілдермен модельдеуге болады: 1 - тәсілі: екілік анықтамалықтың қосылғыш мәнін модельдеу предикатын қолдану арқылы, яғни мұндай жағдайда тамырлар мәндерімен сәйкес келуі керек. 2 - тәсілі: random және tree депаталатын предикаттарын ауыстыру арқылы. Мұндағы мәндерді Tree - member2 көмегімен тексеру керек. Сонда екілік анықтамалықты Tree - Insert предикаты көмегімен қоса аламыз. Мысалы: random предикатын аралығында алсақ, онда оның аралығы 0 мен 99 арасында орналасады. Екілік анықтамалық құрамындағы минималды элементтерді жою үшін өзге предикат қажет болады. Оның құрамы екі сөйлемнен тұратын болады. Егер тамыр жойылса, онда нәтижесінде оң бұтақтар қалады. Төменде екілік анықтамалықтардың минималды элементтерін жоюға көмекші предикатар келтірілген: tree_del_min(tr(X,empty,R), R, X). tree_del_min(tr(K,L,R), tr(K,L1,R), X):- tree_del_min(L, L1, X). Ағаштың биіктігіндегі элементті жоюға арналған негізгі предикат келесідей түрде келтіріледі: tree_delete(X,tr(X,empty,R), R):-!. tree_delete (X,tr(X,L,empty), L):-!. tree_delete (X,tr(X,L,R), tr(Y,L,R1)):- tree_del_min(R,R1, Y). tree_delete (X,tr(K,L,R), tr(K,L1,R)):- X tree_delete (X,tr(K,L,R), tr(K,L,R1)):- tree_delete (X,R,R1). Екілік анықтамалықтың тізімдерін көбейтуге арналған предикат құрайық. Предикат екі аргументті болады. Біріншісі кіріс көбейткішті тізім, ал екіншісі шығыс көбейткішті, яғни бірінші элемент аргументтерінен құрылған екілік анықтамалық. Ағашқа тізімді рекурсивті қосайық. Бос тізімдерден бос ағаш құру бізге рекурсивті базисті береді. Пролог тілінде келесідей болады: list_tree([],empty). /* бос тізімге бос ағаш сәйкес келеді */ list_tree([H|T],Tr):- list_tree(T,Tr1), /* Tr1 - ағаш, шығыс элементтерінің соңынан құрылған */ tree_insert(H,Tr1,Tr). /* Tr - ағаш, тізімнің бас жағын Tr1 ағашына сәйкестегеннен пайда болған */ Кері қайтару предикатын құрайық. Ол предикатта екі аргументті болады. Біріншісі кіріс - көбейетін екілік анықтамалық, ал екіншісі шығыс - бірінші аргумент элементтерінен құрылған тізім. tree_list(empty,[]). /* бос ағашқа бос тізім сәйкес келеді*/ tree_list(tr(K,L,R),S):- tree_list(L,T_L), /* T_L - тізім, сол жақ бұтақ элементтерінен құрылған*/ tree_list(R,T_R), /* T_L - тізім, оң жақ бұтақ элементтерінен құрылған */ conc(T_L,[K|T_R],S). /* S – тізім, T_L тізімдерін біріктіргеннен пайда болған и [K|T_R] */ List tree және Tree - list предикаттары арқылы тізімдерді реттеуге болады. Сонда Пролог мына түрде болады: sort_listT(L,L_S):- list_tree(L,T), /* T- екілік анықтамалық, L шығыс тізімінен құрылған */ tree_list(T,L_S). /* L_S - тізім, T екілік анықтамалық элементтерінен құрылған */ Мұнда тізімдер элементері өзгермейді. жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|