Поиск максимального и минимального элемента в списке
Определение длины списка
Число элементов в списке можно подсчитать при помощи рекурсивных предикатов count_list1 и count_list2. Предикат count_list1 ведёт подсчёт числа элементов в списке на прямом ходе рекурсии, начиная от головы списка, при этом первый параметр типа byte является текущим счётчиком, а второй - необходим для возвращения результата при выходе из рекурсии. Предикат count_list2 ведёт подсчёт числа элементов в списке на обратном ходе рекурсии, начиная с последнего элемента, при этом параметр типа byte является текущим счётчиком и результатом одновременно. Два варианта решения задачи приводятся в примере 39.
Найти максимальный или минимальный элемент в списке можно при помощи рекурсивных предикатов max_list и min_list. Предикат max_list ищет максимальный элемент в списке на прямом ходе рекурсии, начиная от головы списка, при этом первый параметр типа integer является текущим максимумом, а второй - необходим для возвращения результата при выходе из рекурсии. Предикат min_list ищет минимальный элемент в списке на обратном ходе рекурсии, начиная с последнего элемента, при этом параметр типа integer является текущим минимумом и результатом одновременно. Два варианта решения задачи приводятся в примере 40.
Пример 40: поиск максимального т минимального элемента в списке.
Сортировка представляет собой переупорядочение элементов списка определенным образом. Назначением сортировки является упрощение доступа к нужным элементам. Для сортировки списков обычно применяются три метода:
· метод перестановки,
· метод вставки,
· метод выборки.
Также можно использовать комбинации указанных методов.
Первый метод сортировки заключается в перестановке элементов списка до тех пор, пока он не будет упорядочен. Второй метод осуществляется при помощи неоднократной вставки элементов в список до тех пор, пока он не будет упорядочен. Третий метод включает в себя многократную выборку и перемещение элементов списка.
Второй из методов, метод вставки, особенно удобен для реализации на Прологе.
Пример 39: сортировка списков методом перестановки (пузырька).
Для удовлетворения первого правила оба списка должны быть пустыми. Для того, чтобы достичь этого состояния, по второму правилу происходит рекурсивный вызов предиката 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:
