Ответ в теме: Максимальный элемент и его номер на Prolog

      Комментарии к записи Ответ в теме: Максимальный элемент и его номер на Prolog отключены
#2619

Возможны различные реализации вашего алгоритма, например:

  • разделить исходный список на первый элемент (Head) и хвост (Tail). Если разделить не удалось — переход на п.3.
    • хвост обработать рекурсивно, вычислив MaxTailValue и MaxTailPos;
    • если MaxTailValue меньше Head — переход на п.3., иначе — вернуть в качестве результата MaxTailValue и MaxTailPos + 1;
  • вернуть в качестве максимума Head, а в качестве порядкового номера — 1.

Для списка из одного элемента наш алгоритм вернет этот элемент и единицу в качестве позиции. В остальных случаях список будет рекурсивно разделяться на голову и хвост. Хвост будет рекурсивно обрабатываться (вычисляя MaxTailValue и MaxTailPos). Если MaxTailValue больше значения головы — то оно и будет являться локальным максимумом, поэтому нужно вернуть его, а к позиции добавить единицу (ведь мы обработали голову). Если же MaxTailValue окажется меньше или равно первому элементу списка, то вернем значение головы и единицу в качестве позиции, реальная позиция этого элемента будет получена на рекурсивном возврате, когда обработаются остальные элементы.

На языке Prolog этот алгоритм можно записать следующим образом:

domains
	element = integer
	list = element*
predicates
	max_pos(list, element, integer)
clauses
	max_pos([Head|Tail], MaxTailValue, MaxPos):-
		max_pos(Tail, MaxTailValue, MaxTailPos),
		MaxTailValue > Head, !, MaxPos = MaxTailPos + 1.
	max_pos([Head|_Tail], Head, 1).
goal
	List = [1,2,3,2,3,4,5,4,3,4,5,6,4,3,2,3],
	max_pos(List, MaxValue, MaxPos).

Вложения: