Пәндердің оқу-әдістемелік кешенінің тізімдемесі
Тақырып №11: Тізімдер. Тізімдерге қолданылатын амалдар. Тізімдерді реттеу тәсілдері
жүктеу/скачать 2.35 Mb.
|
| Тақырып №11: Тізімдер. Тізімдерге қолданылатын амалдар. Тізімдерді реттеу тәсілдері.
Тізімдерді көпіршікті тәсілмен және алмастыру арқылы реттеу. Таңдау бойынша реттеу. Жылдам реттеу. Біріктіру арқылы реттеу Тізім – реттелген обьект жиынтығы. Ол тік жақшаға алынған тізім элементтерінен тұрады. Тізім элементтерінің саны оперативтік жады көлеміне қарай анықталады. Программада тізімді қолдану үшін домендер бөлімінде тізімдер сипатталуы керек. Бұл тізімдегі барлық обьектілер бір доменге тиісті болуы керек. Тізім элементтері типі жанадағы жұлдызша элементтер санының кез келген болатындығын білдіреді. Тізімді хабарлау: Domains G1=integer* G2=symbol* predicates F [G1] F [G2] Мысалы, Domains List1=integer* List2=symbol* Predicates Name [List1] Score [List2] Clauses Name [“Сәкенұлы”,”Қайратова”,”Талғатұлы”] Score[1,2,3,4] Goal Name[x] Name[y,_] Name[x,_,y,_] Тізім бос болуы да мүмкін. Бұл жағдайда бос тік жақшалар көрсетіледі. Тізім басы, тізімнің алғаш элменттері де болады. Ал қалған элементтері тізім аяғы және құйрығы болады. Олар “|’ (тік жақша) арқылы ажыратылады. Тізімдермен жұмыс оның басы мен аяғына бөлінуіне негізделген. Тізімді басы мен аяғына бөлу, оны рекурсивті бөлуге мүмкіндік береді. Тізі келесі түрде жазылады: [Head|Tail] Тізім мазмұнын басып шығару программасы: Domains List1=integer* List2=symbol* Predicates Print_List (List 1) Print_List (List 2) Clauses Print_list ([]) Print_List([Head|Tail]):-write (Head), nl, Print_List (Tail) Goal Print_List ([1,2,3,4]) Тізімге тиістілік. Тізімге тиістілік тиісті (Х, L) қатынасы арқылы көрсетіледі. Мұндағы X обьект, L-тізім. Тиісті (Х, L) мақсаты ақиқат болады. Егер X, L-тізімде бар болса, тізімге тиістілік анықталады да, мына түсініктер пайдаланылады. X L-дің басы болады немесе X L-дің аяғына тиісті болады.Бұл түсініктерді ереже түрінде жазайық: Тиісті (X, [X|аяғы]) Тиісті (X, [Басы|Аяғы]):-тиісті (X, аяғы) Біріктіру операциясы (конкатенация). Тізімдерді біріктіру операциясын орындауда конк(А1, А2,А3) қатынасын анықтаймыз. Мұндағы А1, А2 берілген тізім, ал А3 оларды біріктергеннен пайда болған тізім. Мысалы, Конк ([a,b], [c,e], [a,b,c,e]) Тізімдермен жұмыс ұйымдастыру көп жағдайда тізім элементтері санын анықтау, қайсыбір шартты қанағаттандыратын элементтерге арифметикалық амалдар қолдану (мысалы элементтердің қосындысы, тақ сандардың көбейтіндісі, теріс элементтердің тізімін алу және т.б.), тізім элементтерін басқа элементпен алмастыру,, өшіру, кірістіру, реттеу әрекеттерін қамтиды. 1 мысал. Тізім элементтерінің қосындысын алу керек болсын. Мұнда бос тізім элементтерінің қосындысын нөлге тең фактісі және тізім аяғы элементтерінің қосындысына тізімнің бірінші элементін, яғни басын қосу идеясын қолданамыз. Head-H, Tail–T деп белгілейік . Sum([], 0). /*бос тізім элементерінің қосындысы 0-ге тең */ Sum([H|T],S):–sum(T, S_T), /* S_T тізім аяғы элементтерінің қосындысы*/ S=S_T+H. /* S берілген тізім элементтерінің қосындысы*/ 2мысал. Тізім элементтерінің арифметикалық ортасын анықтау керек. Бұл есепті шешуде рекурсияны да қолдануға болады, бірақ біз алдыңғы есепте қолданылған қосындыны пайдаланамыз. Avg([ ],0):-! . /*тізім бос болса, процесті тоқтату*/ Avg (L,A) :- Summa(L,S), /*S элементтер қосындысын айнымалылыар қатарына кірістіреміз*/ Length(L,K), /*K айнымалысы элементтер санына тең*/ A=S/K, /*А арифметикалық орта S/K қатынасына тең*/ Мұнда А аргументін Predicates бөлімінде сипаттау барысында real нақты тип деп көрсету керек, себебі бөлу нәтижесінде бүтін сан шықпауы да мүмкін. 3 мысал. Тізімнің ең кіші элементін анықтау керек. Есепті шешуде рекурсияны қолданамыз. Рекурсия базисі ретінде бос тізінің минималды элементі түсінігінің мағынасы жоқ болғандықтан бір элементті тізімнің минималды элементі сол элементтің өзі болатындығын көрсетеміз. Рекурсия қадамы: тізімнің бірінші элементі мен тізім аяғының минималды элементін салыстырып минималды элементті анықтау–осы тізімнің мин.элементі болады. Min_list ([X], X). /*бір элементті тізімнің мин элементі сол элементтің өзі болады*/ Min_list ([H|T], M):- Min_list (T, M_T), /*M_T тізім аяғының мин элементі болады*/ Min (H, M_T, M). /*M – H тізім басы мен M_T-ң минимумы болады*/ Тізімді реттеу дегеніміз– тізім элементтерін қайсыбір ретпен орналастыру. Мысалы, элементтердің өсу ретімен реттелуі. Тізімдерді реттеудің көптеген алгоритмдері бар. Реттеу алгоритмінің екі класы бар: негізгі жадыда түгелдей толық орналасқан мәліметтерді реттеу–ішкі реттеу және сыртқы жадыда орналасқан файлдарды реттеу –сыртқы реттеу. Біз ішкі реттеуді қарастырамыз. Ішкі реттеудің бірнеше танымал тәсілдері бар: көпіршікті реттеу, ол тікелей алмастыру не қарапайым алмастыру деп те аталады; таңдау; алмастыру; біріктіру; жылдам реттеу тәсілдері де бар. Көпіршікті реттеу әдісінің идеясы былайша болады: Әрбір қадамда тізімнің қатар орналасқан көршілес элементтері салыстырылады. Егер дұрыс орналаспаса, яғни алдыңғы элемент келесі элементтен кіші болса, олар орындарын ауыстырады. Бұл процесс дұрыс ретпен орналаспаған элементтер жұбы реттелгенше жүргізіле береді. Көпіршікті әдісте әрбір жұп салыстыру барысында минималды элементтер тізім басына жылжытылып отырады. 2 предикатты қолданып көпіршікті әдіспен тізімді реттеуді ұйымдастырайық: 1-ші предикат permutation, тізім басындағы 2 элементті салыстырады, егер бірінші элемент екіншісінен үлкен болса, орнын алмастырады. Егер дұрыс орналасса бұл предикат тізім аяғына ауысады. 2-ші предикат–негізі предикат–bubble тізімге көпіршікті реттеу жүргізеді, ол өз әрекеттерінде permutation предикатын қолданады. permutation ([X,Y|T],[Y,X|T]):- X>Y,! /*тізімінің 1,2 элементтері 1>2-шіден болса орын алмасады. */ permutation ([X|T], [X|T1]):- Permutation(T,T1) /* тізім аяғы элементтерін ауыстыруға көшу*/ Bubble (L, L1):- Permutation (L,LL), /* алмастыру жүргізетін предикатты шақыру*/ !, Bubble (LL, L1) /* алынған тізімді қайта тексеру, қажет болса реттеу жүргізу*/ Bubble (L, L). /* егер алмастыру болмаса, онда тізім реттелген*/ Алмастыру арқылы реттеу егер тізім аяғы реттелген болса, онда тізім басын қажетті позицияға (тізім аяғындағы) орналастыру қажет идеясына негізделген. Бұл идеяны жүзеге асыру үшін екі предикат құрамыз: Insert – мәнді кірістіру предикаты тізім басын тізім аяғына реттелетіндей етіп кірістіреді. Предикат 3 аргументтен тұрады 1-ші кірістірлетін элемент –тізім басы, 2-ші реттелген тізім –тізім аяғы, 3-ші –1-ші аргумент кірістірілген 2 аргументтен тұратын тізім. ins_sort реттеу жұмысын ұйымдастыратын негізгі предикат. Бірінші аргументі реттеуді қажет ететін тізім болады, екінші аргументі алдыңғы тізім элементтерінен тұратын реттелген тізім болады. ins_sort([], []). /*реттелген бос тізім бос тізім болып қалады*/ ins_sort([H|T], L):- ins_sort(T,T_Sort), /*T–берілген тізім аяғы, T_Sort– берілген тізімнің реттелген аяғы*/ Insert(H, T_Sort, L) /*берілген тізім басы H-ты T_Sort-қа кірістірп, элементтері өсу ретімен орналасқан L тізімін аламыз*/ Insert (X,[],[X]). /*бос тізімге кез келген элементті кірістіргеннен бір элементтік тізім аламыз*/ Insert(X,[H|T],[H|T1]):- X>H, !, /* егер кірістірілетін элемент тізім басынан үлкен болса, онда оны тізім аяғына кірісітіру керек*/ Insert (X,T,T1). /* Х-ті Т тізімінің аяғына кірістіріп Т1 тізімін аламыз*/ Insert (X,T,[X|T]). /* алдыңғы қиып тастау ! ережесі нәтижесінде орындалады, және кірістірілетін элемент тізімнің басынан үлкен болмаса ғана тізімніің бірінші элементі ретінде кірістіріледі*/ Таңдау бойынша реттеу. Бұл әдіс бойынша реттеу өте қарапайым. Тізімнен минималды элемент табылады да, delete_on предикаты бойынша өшіріледі. Қалған тізімді реттеп, ең кіші элементті тізім басына орналастырады, бұл бәрінен кіші элемент болғандықтан тізім ретін бұзбайды. Choice([],[]). Choice(L,[X|T]):- Min_list(L,X), /*L тізімінің X мин элементін T реттелген тізімге кірістіру*/ /*X –L тізімінің мин элементі*/ Delete_on (X,L,L1), /* L1 – X элементі өшірілген L тізімі*/ Choice(L1,T). /*L1-ді реттеп, T тізімін аламыз*/ Жылдам реттеу тәсілінің авторы Хоар, бұл тәсілдің бұлайша аталуы орындалу алгоритмінің тиімділігінің жоғарылығында, яғни жылдамдығында. Реттеу алгоритмін былай сипаттауға болады: Тізім ішінен қандай да бір «барьера» (ажыратушы) қызметін атқаратын элемент таңдалынып, тізім екі ішкі тізімге бөлінеді. Біреуіне «барьерлік» элементтен кіші элементтерді орналастырады. Екіншісіне барьерлік элементтен үлкен не тең элементтер орналастырылады. Екі тізім де осы әдіспен қайта реттеледі. Бұл реттеу процесі тізім элементтерінің санына қарай бірнеше рет қайталануы мүмкін. Содан соң барьерлік элементтен кіші элементтер, барьерлік элементтің өзі, соңынан барьерлік элементтен кіші емес элементтер орналастырылады да нәтижесінде реттелген тізім алынады. Программа жазу үшін бірнеше предикат қолданылады: жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|