Пошук максимального і мінімального елемента в списку
Визначення довжини списку
Число елементів в списку можна підрахувати за допомогою рекурсивних предикатів count_list1 і count_list2. Предикат count_list1 веде підрахунок числа елементів в списку на прямому ході рекурсії, починаючи від голови списку, при цьому перший параметр типу byte є поточним лічильником, а другий - необхідний для повернення результату при виході з рекурсії. Предикат count_list2 веде підрахунок числа елементів в списку на зворотному ході рекурсії, починаючи з останнього елемента, при цьому параметр типу byte є поточним лічильником і результатом одночасно. Два варіанти вирішення завдання наводяться в прикладі 39.
Приклад 39: визначення довжини списку.
count_list1 ([_ | T], N, M): - N1 = N + 1, count_list1 (T, N1, M).
count_list1 ([_ | T], N): - count_list1 (T, N1), N = N1 + 1.
Знайти максимальний або мінімальний елемент в списку можна за допомогою рекурсивних предикатів max_list і min_list. Предикат max_list шукає максимальний елемент в списку на прямому ході рекурсії, починаючи від голови списку, при цьому перший параметр типу integer є поточним максимумом, а другий - необхідний для повернення результату при виході з рекурсії. Предикат min_list шукає мінімальний елемент в списку на зворотному ході рекурсії, починаючи з останнього елемента, при цьому параметр типу integer є поточним мінімумом і результатом одночасно. Два варіанти вирішення завдання наводяться в прикладі 40.
Приклад 40: пошук максимального т мінімального елемента в списку.
max_list (list, integer, integer)
max_list ([H | T], N, M): - H> N, max_list (T, H, M).
max_list ([H | T], N, M): - H<=N, max_list(T,N,M).
min_list ([H | T], M): - min_list (T, M1), H> M1, M = H.
min_list ([H | T], M): - min_list (T, M1), H<=M1, M=M1.
Сортування є переупорядочение елементів списку певним чином. Призначенням сортування є спрощення доступу до потрібних елементів. Для сортування списків зазвичай застосовуються три методи:
Також можна використовувати комбінації зазначених методів.
Перший метод сортування полягає в перестановці елементів списку до тих пір, поки він не буде впорядкований. Другий метод здійснюється за допомогою кількаразового вставки елементів в список до тих пір, поки він не буде впорядкований. Третій метод включає в себе багаторазову вибірку і переміщення елементів списку.
Другий з методів, метод вставки, особливо зручний для реалізації на Пролозі.
Приклад 39: сортування списків методом перестановки (бульбашки).
Приклад 40: сортування списків методом вставки.
insert_sort (list, list)
insert (integer, list, list)
asc_order (integer, integer)
insert_sort ([H1 | T1], L2): - insert_sort (T1, T2),
insert (X, [H1 | T1], [H1 | T2]): - asc_order (X, H1).
insert (X, L1, [X | L1]).
asc_order (X, Y): - X> Y.
insert_sort ([4, 7, 3, 9], L).
Для задоволення першого правила обидва списки повинні бути порожніми. Для того, щоб досягти цього стану, по другому правилу відбувається рекурсивний виклик предиката insert_sort, при цьому значеннями H1 послідовно стають все елементи вихідного списку, які потім поміщаються в стек. В результаті вихідний список стає порожнім і за першим правилом вихідний список також стає порожнім.
Після того, як відбулося успішне завершення першого правила, Пролог намагається виконати другий предикат insert, виклик якого міститься в тілі другого правила. Змінної H1 спочатку присвоюється перший взяти з стека значення 9, а предикат приймає вид insert (9, [], [9]).
Так як тепер задоволено все друге правило, то відбувається повернення на один крок рекурсії в предикате insert_sort. З стека витягується 3 і по третьому правилу викликається предикат asc_order, тобто відбувається спроба задоволення п'ятого правила asc_order (3, 9): - 3> 9. Оскільки дане правило закінчується неуспішно, то неуспішно закінчується і третє правило, отже, удовлетворяетсячетвертое правило і 3 вставляється у вихідний список зліва від 9. insert (3, [9], [3, 9]).
Далі відбувається повернення до предикату insert_sort. який приймає наступний вигляд: insert_sort ([3, 9], [3, 9]).
На наступному кроці рекурсіііз стека витягується 7 і по третьому правилу викликається предикат asc_order у вигляді asc_order (7, 3): - 7> 3. Оскільки дане правило закінчується успішно, то елемент 3 забирається в стек і insert викликати рекурсивно ще раз, але вже з хвостом списку - [9]: insert (7, [9], _). Так як правило asc_order (7, 9): - 7> 9 закінчується неуспішно, то виконується четверте правило, відбувається повернення на попередні кроки рекурсії спочатку insert, потім insert_sort.
В результаті 7 поміщається у вихідний список між елементами 3 і 9. insert (7, [3, 9], [3, 7, 9]).
При поверненні ще на один крок рекурсіііз стека витягується 4 і по третьому правилу викликається предикат asc_order у вигляді asc_order (4, 3): - 4> 3. Оскільки дане правило закінчується успішно, то елемент 3 забирається в стек і insert викликати рекурсивно ще раз, але вже з хвостом списку - [7, 9]: insert (4, [7, 9], _). Так як правило asc_order (4, 7): - 4> 7 закінчується неуспішно, то виконується четверте правило, відбувається повернення на попередні кроки рекурсії спочатку insert, потім insert_sort.
В результаті 4 поміщається у вихідний список між елементами 3 і 7:
insert (4, [3, 7, 9], [3, 4, 7, 9]).
insert_sort [4, 7, 3, 9], [3, 4, 7, 9]).