Объединение множеств на Prolog

      Комментарии к записи Объединение множеств на Prolog отключены

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

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

    Задача:

    Множества заданы списками целых чисел L1 и L2. Получить в виде списка L3 множество, представляющее собой объединение L1 и L2.

    Нужно решить на Visual Prolog и SWI Prolog.

    В условии сказано, что даны множества, т.е. можно полагать, что в исходных списках элементы не повторяются. Тогда, чтобы получить объединение множеств, можно последовательно выбирать элементы из первого множества и при их отсутствии во втором множестве — дописывать элемент к результату. Когда элементы первого множества кончатся — добавить к результату целиком второе множество, ведь выходит, что ранее в результат были добавлены только те элементы, которые во втором множестве отсутствуют.

    Изобразить этот процесс можно с помощью следующей блок-схемы:
    union_of_sets_flowchart

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

    На языке Prolog проверка вхождения элемента в список выполняется с помощью предиката member, который встроен во множество диалектов. Если в вашей реализации языка такой предикат отсутствует — возьмите его из статьи «Обработка списков в Prolog«.

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

      union_of_sets([], Union, Union):-!.
      union_of_sets([Head|Tail], Set, Union):-
        member(Head, Set), !,
        union_of_sets(Tail, Set, Union).
      union_of_sets([Head|Tail], Set, [Head|UnionTail]):-
        union_of_sets(Tail, Set, UnionTail).

    Обратите внимание, что во втором правиле предиката union_of_sets используется отсечение, препятствующее запуску механизма поиска с возвратами. Подробнее про использование оператора отсечения смотрите в статье «оператор отсечения (cut) и неудачи (fail) в Prolog«.

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