Пролог: Нахождение второго по величине элемента в списке

Here's one way of doing it O(n). First off, the starting predicate, (slne/2). Given we're after the 2nd largest element, we'll assume you have an input list (of numbers) with length of at least two. Kick things off by comparing the relative values of the first two elements and record the current maximum and the current '2nd largest' (as suggested earlier, by Priyank), as arguments to a call to another predicate to do the work (slne/4):

slne([E0, E1|Es], Res) :-
    E0 > E1, !,
    slne(Es, E0, E1, Res).
slne([E0, E1|Es], Res) :-
    slne(Es, E1, E0, Res).

Secondly, now that we've got a starting point of reference, recurse through the remainder of the list (if any) and return the second largest element (SecMax), in (slne/4).

The base case: No more elements left! We're finished.

slne([], _, Res, Res).

The next case: we find a new local maximum at the start of the list:

slne([E|Es], Max, _SecMax, Res) :-
    E >= Max, !,
    slne(Es, E, Max, Res).

(Note that we threw away the current second largest (SecMax), because we assume that it was smaller than or equal to Max).

The next case: we don't find a new local maximum, but we do find a new '2nd best':

slne([E|Es], Max, SecMax, Res) :-
    E >= SecMax, !,
    slne(Es, Max, E, Res).

The last case: Throw away other values, as they're irrelevant - look at the rest instead:

slne([_|Es], Max, SecMax, Res) :-
    slne(Es, Max, SecMax, Res).

That's it. Personally, I like Juanjo's solution, mainly because it's 1 line of code, and the performance difference between O(n log n) and O(n) might be negligible in practice even for large input. (Also note that dsort/2 doesn't appear in all PROLOG implementations - e.g., in SWI-PL, you might try msort/2 instead).

Не знаю о прологе, но в целом нельзя хранить две переменные, одну для наивысшей, а другую для второй.

if(a >= x)
  b = a
  a = x

Я расскажу вам два разных алгоритма. Первый простой, второй немного сложный.

1. Напишите функцию сортировки слиянием (по убыванию), а затем просто выберите второй элемент. Это легко, но это занимает O (nlogn) времени.

2. В общем, для любого k вы можете решить эту проблему с помощью следующего алгоритма. Это выполняется за линейное время.

- Разбейте список на группу из пяти элементов
- Найдите медианное значение для каждой группы, что может быть выполнено с фиксированным числом сравнений
--Рекурсивно находите медианы или медианы
--Разделить исходный список по медианам медиан
--Рекурсивно найдите k-й по величине элемент в соответствующем меньшем списке.

Вы можете найти более подробное обсуждение этого алгоритма в главе 9 «Введение в алгоритмы Кормена»

Я бы порекомендовал вам попробовать реализовать его на ваш собственный, не видя существующей реализации Мне было очень интересно реализовать этот алгоритм в прологе :)

Вот как вы это делаете в Прологе:

secondLargest(L, Y) :- dsort(L, [X,Y|T])

Где dsort работает так:

?- dsort([2,3,4,2,1], L).
L = [4,3,2,2,1]

Вы можете реализовать dsort самостоятельно, хакерская часть - это то, как я написал список [X , Y | T]. Вот читаем: список состоит из 2 элементов (X и Y) и хвоста (T).

Это идиома, которая может использоваться на любом языке:

Прокрутите список, подсчитайте каждый элемент и вставьте в другой список данные, чтобы указать элемент и его размер. Отсортируйте список в порядке убывания. Переместите указатель списка на второй элемент. Теперь у вас второй по величине элемент.

Первая задача: реализовать предикат сортировки, если сейчас это выходит за рамки ваших возможностей, посмотрите в Clocksin and Mellish.

Вторая задача: напишите предикат, который выбирает начало хвоста список. Примените этот предикат к вашему отсортированному списку.

ИЛИ, поскольку вы уже знаете, как выбрать самый большой элемент в списке, написать предикат, чтобы отбросить самый большой элемент списка, и применить существующий предикат к оставшейся части оригинала список.

другой (очевидно, не самый лучший) подход был бы следующим: 1. найти максимальный элемент в списке L 2. удалить максимальный элемент из списка L и получить новый список L1 3. найти max в L1 и вернуть его