Търсене максимален елемент в списъка
Определяне на дължината на списъка
Броят на елементите в списъка може да се брои с помощта на рекурсивни предикати count_list1 и count_list2. Предикатна count_list1 следи броя на елементите в списъка на прав ход на рекурсията, от списъка на главата, където първият параметър е настоящ тип байт брояч, а вторият - е необходимо да се върне в резултат на изхода на рекурсията. Предикатна count_list2 следи броя на елементите в списъка на обратния ход на рекурсия, започвайки с последния елемент, където тип параметър е текущата байт брояч и резултатът едновременно. Два варианта за решаване на проблема са дадени в Пример 39.
Пример 39: Идентификация на дължините на списък.
count_list1 ([_ | Т], М, М) - N1 = N + 1, count_list1 (T, N1, М).
count_list1 ([_ | Т], N): - count_list1 (T, N1), N = N1 + 1.
Намерете максималната или минимална елемент в списъка, можете да използвате рекурсивни предикати max_list и min_list. Предикатна max_list търси максималния елемент в списъка, за да ръководи процеса на рекурсия, като се започне от главата на списъка, първият параметър от тип цяло число е пика на тока, а вторият - е необходимо да се върне в резултат на изхода на рекурсията. Предикатна min_list търсят минималната елемент на списъка на обратния ход на рекурсия, започвайки с последния елемент, където тип параметър число е настоящ минимум и резултатът едновременно. Два варианта за решаване на проблема са дадени в Пример 40.
Пример 40: намери максималния елемент минимум m в списъка.
max_list (списък, число, число)
max_list ([Н | Т], М, М): - H> N, max_list (Т, Н, М).
max_list ([Н | Т], М, М): - Н<=N, max_list(T,N,M).
min_list ([Н | Т], M): - min_list (T, М1), Н> M1, М = Н.
min_list ([Н | Т], M): - min_list (T, М1), Н<=M1, M=M1.
Сортирането е пренареждане на списък елементи в определен начин на. Целта на окачествяване е да се опрости достъпа до желаната опция. За да сортирате списъците са обикновено се използват три метода:
Също така е възможно да се използват комбинации от тези методи.
Първият метод е да сортирате пермутация на елементи от списъка, докато той няма да бъде поръчан. Вторият метод се извършва с помощта на повтаряща вмъкване на елементи в списъка, докато той няма да бъде поръчан. Третият метод включва много проби и преместване на елементи в списъка.
Вторият метод, метод на вмъкване е особено подходящ за прилагане на Prolog.
Пример 39: Подреждане списъци пермутация метод (балон).
Пример 40: сортиране метод вмъкване списъци.
insert_sort (списък, списък)
вмъкнете (число, списък, списък)
asc_order (число, число)
insert_sort ([H1 | Т1], L2): - insert_sort (Т1, Т2),
поставете (X, [H1 | Т1], [H1 | Т2]): - asc_order (X, H1).
вмъкнете (X, L1, [X | L1]).
asc_order (X, Y): - X> Y.
insert_sort ([4, 7, 3, 9], L).
и в двата списъка, трябва да бъдат празни, за да се отговори на първото правило. За да се постигне това състояние, второто правило се случва insert_sort предикат рекурсивно повикване, H1 на стойност последователно превръща оригинални елементи от списъка, които след това се поставят в купа. В резултат на това първоначалния списък се изпразни и първото правило в списъка с продукция също се изпразни.
След като имаше успешното приключване на първото правило, Prolog опитва да извърши втори вложка предикат, обаждането се съдържа в текста на второто правило. Първо променлива H1 се определя е взета от стека 9 първата стойност и предикат се вложката форма (9, [], [9]).
Тъй като в момента се удовлетворява всички второто правило, тя ще се върне към една стъпка рекурсия в insert_sort предикатното. 3 от комина се отстранява и третото правило се нарича asc_order предикат, което означава, че е опит да се отговори на петото правило asc_order (3, 9): - 3> 9. Тъй като правило не успее, не успяха и завършва третото правило, следователно, обикновено udovletvoryaetsyachetvertoe и 3 се вмъква в списъка на изхода отляво на 9. вложка (3, [9], [3, 9]).
Следваща има връщане към insert_sort предикатното. който се следната форма: insert_sort ([3, 9], [3, 9]).
В следващата стъпка rekursiiiz стека 7 се отстранява и третото правило се нарича предикат asc_order asc_order (7, 3): - 7> 3. Тъй като правило е успешен, елемент 3 е прибран в стека и поставете vyzvaetsja рекурсивно отново, но с опашката на списъка - [9]: поставете (7, [9], _). Тъй като обикновено asc_order (7, 9): - 7> 9 провали, четвъртото правило се изпълнява, процесът се връща към предишния стъпки рекурсия първо вмъкнете, след insert_sort.
В резултат, на изхода 7 се поставя в списъка между елементите 3 и 9. вложката (7 [3, 9], [3, 7, 9]).
При връщане на допълнителен етап на стека се отстранява rekursiiiz 4 и третото правило се нарича предикат asc_order asc_order (4, 3): - 4> 3. Тъй като правило успешно, елемент 3 е прибран в стека и поставете vyzvaetsja рекурсивно отново, но със списък опашка - [7, 9]: втулката (4, [7, 9] _). Тъй като обикновено asc_order (4, 7): - 4> 7 се провали, четвъртото правило се изпълнява, процесът се връща към предишния стъпки рекурсия първо вмъкнете, след insert_sort.
В резултат, изходът 4 се поставя в списъка между елементите 3 и 7:
поставете (4 [3, 7, 9], [3, 4, 7, 9]).
insert_sort [4, 7, 3, 9], [3, 4, 7, 9]).
Свързани статии