Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
partiton( T,H,L,G), Т тізімін L(Н барьерлі элементінен кіші элементтер тізімі) жəне G (Н-тан кіші емес элементтер тізіміне) тізімді бөлеміз. * / quick _ sort(L,L _ s), /* L_s тізімі – L тізімінің элементтерін реттеу нəтижесі */ quick. _sort(G,G _s), Аналогты, G~s тізімі – G тізімдегі элементтердің реттелу нəтижесі. * / conc(L _s,[HG._s],O). /* L_s тізімдерінің басы Н тізімімен қосылуы, ал G_s соңы. Нəтижесін О деп белгілейміз * / . partition([],_,[],[]). /* бос тізімдердің элементтерін қалай бөлсекте, бос тізімнен босқа еш нəрсе алмаймыз*/ partition([XIT] Y,[XT1 ],Bs):- Х<У,!, partition(T,Y,Tl,Bs). /* егер Х элементі У кедергі элементінен кіші болса, онда оның үшінші аргументін қосамыз. * / partition([XT У,Т1 ,[XBs ]):- раrtition(Т, У, Тl ,Bs). /* кері жағдайда оны төртінші аргументке жазамыз * / Сұрттаудың келесі алгоритмін зерттеуге көшпей жатып, бір қосалқы есепті шығарайық. Бізде реттелген екі тізім бар болсын, жəне біз олардың элементтерін қосылған тізім-сұртталған түрде қалатындай етіп олардың элементтерін қосқымыз. Предикатты жүзеге асыру ойы , екі сортталған тізімнің тəртіпті сақтауымен қосуды орындауы айтарлықтай қарапайым. Əр қадамда реттелген тізімдердің бастарын салыстырып отырамыз, онда ең кішісін салдарлы тізімге көшіреміз. Солай тізімдердің бірі біткенше қыламыз. Тізімдердің біреуі босағанда, бос емес тізімдегі қалдықты жазу қалады. Нəтижесінде алғашқы екі тізімнен тұратын тізім аламыз,;, Жəне олардың элементтерінін орналасуы керек орында. Берілген сипаттаманы жүзеге асыратын предикат құрайық (оны fusion деп атайық). Тізімдердің қайсысы бірінші босайтынын білменгеннен кейін, бізге рекурсияны екі базалық тізім бойынша қуу керек. Бізде екі факт болады – рекурсия негізі егер біз кейбір тізімді бос тізіммен қоссақ, онда біз нəтижелінде сол тізімді аламыз. Бірінші тізім бос кезінде жəне екінші тізім бос кезінде бұл факт орын алады. Рекурсия қадамын екі ереже береді: біріншісі - егер бірінші тізімнің басы екінші тізімнің басынан кіші болса, онда дəл бірінші тізім басын салдарлайтын тізім ретінде жазу керек, одан кейін бірінші тізім соңының екіншісімен қосылуына көшу керек. Бұл қосылудың нəтижесі ақырғы тізімнің соңы болып келеді. Екінші ереже керісінше, салдарлы тізім басы ретінде екінші тізімнің басын толықтырып отырады жəне бірінші тізімді екінші тізім соңымен қосады. fusion(Ll,[ ],Ll):-! /* Ll тізімі бос тізіммен қосқанда L 1 тізімін аламыз * / fusion([ ],L2,l '):-/* L2 тізімі бос тізіммен қосқанда L2 тізімін аламыз * / fusion([H1T1],[H2T2],[H1T]):- Н1<Н2,!, /* егер Нl бірінші Н2 тізімнің басынан кіші болса / fusion(T1, [Н2Т2],Т). /* бірінші тізімнің Т1 аяқ жағын екінші тізіммен қосамыз [Н2Т2] * / fusion(L1, [Н2T2],[Н2Т]):- fusion(L1,Т2,Т). / L 1 бірінші тізімді Т2 екінші тізім соңымен қосамыз * / Енді қосу арқылы сорттау алгоритмін анықтауға көшуге болады. Қосу арқылы сұрыптау Қосылу əдісі – “ежелгі” сұрыптардың алгоримдерінің бірі. 1945 жылы Джон фон Нейман ойлап тапқан. Бұл ой келесіде негізделген. Екі тізімге реттеу үшін тізімді бөлеміз. Осы элементтердің əр-қайсысын сол əдіспен реттейік, одан кейін реттелген тізімшелерді қайта ортақ бір тізімге қосамыз. Алғашқы тізімді екіге бөлетін, бірінші предикат құраймыз. Ол екі факттен жəне ережелерден тұратын болады. Бірінші факт бос тізімді екі бос тізімге болады деп тұжырымдайды. Екінші факт бір элементті тізімнің сол бір элементті тізімге жəне бос тізімге бөлінуін тұжырымдайды. splitting([],[],[])./* бос тізімді тек бос тізімшелерге бөлуге болады * / sрlittiпg([Н],[Н],Ш. /* бір элементті тізімді тек бір элементті тізімге бөлуге болады * / splitting([H1 ,Н2Т],[Н1Т1 ],[Н2Т2]):- splitting(T,Tl,T2). /* Н1 элементті бірінші тізімшеге жібереміз, Н2 элементті – екінші тізімшеге жібереміз, Т арт жағын Т1 жəне Т2 тізімшелерге бөлеміз.*/ Енді негізгі предикатты жазуға кірісуге болады жəне ол тізімді сорттауды жүзеге асырады. Ол үш ұсыныстан тұратын болады. Біріншісі анық фактті деклорациялайды. Бос тізімді сұрыптағанда, бос тізім шығады. Екіншісінде бір элементті тізім реттелген болып келеді дейді. Үшінші ережеде қосылу сұрыптаудың əдісінің мəні бар. Басында splitting предикатының көмегімен тізімшелер екіге бөлінеді, содан олардың əр-қайсысы fusion sort предикаты рекурсивті шақырумен сұрыпталады, жəне, соңында, fusion предикатын қолдану арқылы, алынған реттелген тізімшелерді бір тізімге қосамыз, жəне ол алғашқы тізім элементтерінің реттелу нəтижесі болып табылады. Бастағы түсініктің баяндамасын жазайық. fusion_soгt([],[]):-!./* сортталған бос тізім бос болып қалады. fusion soгt([H] [H]):-I. /* бірэлементті тізім реттелген*/ fusiоп_sоrt(L,L _s):- splitting(L,L 1 ,L2), /* L тізімін екі тізімшеге бөлеміз. * / fusion _sort(Ll,Ll_s), /* Ll_s - Ll сұрыптарын жүзеге асырады.*/ fusion sortCТ~2,L2 s), /* L2_s - L2 сұрыптарын жүзеге асырады. */ fusion(L 1_ s,L2 _ s,L _s). /* L s тізіміне Ll s и L2 s қосамыз */ Келесі этапта екі элементті тізімдер т.б. қосылады. Соңғы қадамда екі тізімше қосылады: нəтижелі, сұрыпталған. Сұрыптау тақырыбын аяқтамасы ретінде, тізімнің реттелгендігендігін тексеретін предикатты өңдейік. Ол тіпті де қиын емес. Тізім реттелген болу үшін, ол немесе бос болуы керек, немесе бір элементті болуы керек, немесе кез-келген жақын элементтер дұрыс тізбекте болуы керек. Осы талқымаларды жазайық. sorted([ ]). /* сұрыпталған бос тізім * / sorted([_])./* бір элементті тізім реттелген * / sorted( [Х, YI Т]):- Х<=У, sorted([Y[T]). /* тізім реттелген, егер бірінші екі элемент дұрыс тізімде орналасса жəне екінші элементпен тізім құрылса * / Орташа жəне минималды мəнді тізімдегі элементтердің суммасын табу қарастырылады;тізімдерді сұрыптау əдістері: көпіршіктік, таңдау арқылы , қыстыру арқылы, жылдам сорттау. жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|