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

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

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Максимальный элемент и его номер на Prolog

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 2 мес. назад.

  • Автор
    Сообщения
  • #2618

    questioner
    Участник

    Здравствуйте. Нужна программа на Visual Prolog, выдающая значение максимального элемента списка целых чисел и его порядковый номер в списке.

    Я смотрел тему про поиск значения максимального элемента списка, но мне нужно найти также и номер. Я не знаю как это сделать, т.к. в отличии от значения, которое я просто беру из списка, порядковый номер элемента нужно вычислять. Я думал над тем, чтобы сначала найти значение, а потом — его позицию в списке с помощью предиката nth0, но мне это решение не кажется оптимальным. Возможно ли решить задачу правильнее?

  • #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).

    Вложения:

Для ответа в этой теме необходимо авторизоваться.