Пәндердің оқу-әдістемелік кешенінің тізімдемесі
жүктеу/скачать 2.35 Mb.
|
| partition предикаты тізімді екі ішкі тізімге бөледі. Ол 4 аргументтен тұрады. Алғашқы екеуі енгізілетін мәндер, яғни бірінші берілген тізім, екіншісі барьерлік элемент, 3 және 4 шығарылатын нәтижелік аргументтер болады. 3-ші аргумент барьерлік элементтен кіші элементтер, 4-ші аргумент барьерлік элементтен кіші емес элементтер тізімі.
quick_sort предикаты Хоардың жылдам реттеу алгоритмін жүзеге асырады. Ол екі сөйлемнен тұрады. Ол partition предикаты арқылы бос емес тізімді екіге бөледі, оларды өздерін қайта-қайта шақыру арқылы рекурсия көмегімен реттейді, содан соң conc предикаты(конкатенация) арқылы оларды біріктіреді. quick_sort ([],[]). /*реттелген бос тізім бәрібір бос тізім болады */ quick_sort([H|T], 0):- partition (T,H,L,G) /*T тізімді H барьерлік элементіне, одан кіші элементтерден тұратын L тізіміне және одан үлкен элементтерден тұратын G тізіміне бөледі*/ quick_sort(L, L_S), /*L_S тізімі реттелген L тізімінің элементтері*/ quick_sort(G, G_S), /*G_S G-ң реттелген түрі*/ conc (L_S, [H|G_S], 0). /*L_S тізімін басы H, аяғын G_S тізімінен біріктіріп 0 тізімін аламыз*/ partition([], _, [], []). /*бос тізімді қанша бөлсе де бос тізім болады*/ partition ([X|T],Y, [Y|T1], Bs):- X Partition ([X|T], Y, T1, [X|Bs]):- Partition(T,Y, T1, Bs) . /*кері жағдайда оны 4-ші аргументке қосамыз*/ Біріктіру арқылы реттеу әдісінің авторы Джон фон Нейман. Әдіс идеясы: реттелуі қажет тізімді екі ішкі тізімге бөлеміз. Олардың әрқайсысын осы тәсіл көмегімен реттейміз және реттелген тізімдерді қайта біріктіріп, үлкен реттелген тізім аламыз. Мұнда splitting (расщеплять) тізімді бір элементтік тізімдерге бөлшектейтін, fusion (слиять) біріктіретін, fusion_sort (сортировка слиянием) және sorted (сортировщик) тізімнің реттелгендігін тексеретін предикаттарды қолданамыз. Splitting([ ], [ ], [ ]). /*бос тізімді бөлшектегеннен тек бос тізімдер алынады*/ Splitting([H],[H],[ ]). /*бір элементті тізімді бір элементтік тізімге және бос тізімге бөлшектеуге болады*/ Splitting([H1,H2|T], [H1|T1], [H2|T2]):- Splitting(T,T1,T2). /*Н1 элементін бірінші ішкі тізімге, Н2-ні 2-ші ішкі тізімге жіберіп, Т тізім аяғын Т1 ж/е Т2 тізімдеріне бөлеміз*/ fusion_sort([ ], [ ]):-!. /*реттелген бос тізім бәрібір бос тізім болады*/ fusion_sort([H], [H]):-! /*бір элементтік тізім әрқашан реттелген*/ fusion_sort(L, L_s):- Splitting(L,L1,L2), /*L тізімін L1 және L2 тізімдеріне бөлшектеу*/ fusion_sort(L1, L1_s), /*L1_s L1 тізімін реттеу нәтижесі*/ fusion_sort(L2, L2_s), /*L2_s L2 тізімінің реттелген түрі*/ fusion_sort(L1_s, L2_s, L_s), /*L1_s пен L2_s-ті біріктіріп L_s тізімін аламыз*/ sorted([]). /*бос тізім әрқашан реттелген*/ sorted([_]). /*бір элементті тізім де реттелген*/ sorted([X,Y|T]):- X<=Y, sorted([Y|T]). Бақылау сұрақтары Тізім деген не? Тізімдерге қандай амалдар қолданылады? Тізім программаның қандай бөлімінде сипатталады? Конкатенация деген не? Ішкі тізім деген не? Тізімді не себеппен басы мен аяғына бөледі? Тізімді сипаттау форматы қандай? Бос тізім бола ма? Тізімге тиістілік операциясы қалай жүргізіледі? Тізімдерді реттеу қандай мақсатта жүргізіледі? Тізімдерді ішкі реттеу және сыртқы реттеу түсінігіне сипаттама беріңіз. Тізімдерді реттеудің қандай тәсілдерін білесіз? Көпіршікті реттеу. Алмастыру арқылы реттеу қалай ұйымдастырылады? Мысал келтіріңіз. жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|