Список элементов, встречающихся более одного раза

      Комментарии к записи Список элементов, встречающихся более одного раза отключены

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

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

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

    Решим задачу на Visual Prolog:

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

    domains 
    	list = integer*
    predicates
      	repeated_elements(list, list)
      	repeated_elements(list, list, list)
    clauses
    	repeated_elements(List, Repeated):-
    		repeated_elements(List, [], Repeated).
    		
    	repeated_elements([], Repeated, Repeated):-!.
    	repeated_elements([Head|Tail], Buf, Repeated):-
    		member(Head, Tail),
    		NOT(member(Head, Buf)), !,
    		repeated_elements(Tail, [Head|Buf], Repeated);
    		repeated_elements(Tail, Buf, Repeated).
    goal
      	repeated_elements([1,2,3,4,5,2,5,6,7,8,6,0,8], X).

    repeated_elements

    В приведенном решении используется предикат member. В ряде реализаций пролога он является встроенным, для других реализаций – его можно взять из темы “работа со списками в Prolog“. С помощью функции member выполняется поиск элемента в списке.

    Повторяющиеся элементы накапливаются в буфере. Основная функция инициализирует буфер пустым списком, вызывая вспомогательную функцию.

    Из списка последовательно выбираются элементы, каждый из них ищется среди оставшихся элементов (он должен там присутствовать) и среди элементов, уже добавленных в буфер (он должен там отсутствовать). Для проверки отсутствия используется оператор NOT. Если все условия выполнены — элемент добавляется в буфер, который обрабатывается рекурсивно вместе с остальными элементами списка. Если хоть одно условие нарушено — то либо текущий элемент не повторяется в списке, либо повторяется несколько раз и такое значение уже было добавлено в буфер, при этом оставшиеся элементы обрабатываются рекурсивно, но значение буфера не изменяется.

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