Ответ в теме: Общие и различные элементы списков (Turbo Prolog)

      Комментарии к записи Ответ в теме: Общие и различные элементы списков (Turbo Prolog) отключены
#2677

Предикат ввода списка на Turbo Prolog уже описывался на форуме. По поводу вашей задачи — алгоритм должен быть следующий:

  1. разделяем первый список на голову (первый элемент, HeadA) и хвост (остальные элементы, TailA);
  2. выполняем поиск элемента HeadA во втором списке — если находим, то:
    1. удаляем Head из второго списка, получаем остаток TailB;
    2. выполняем рекурсивную обработку TailA и TailB, получаем TailCommonList и MiscList;
    3. добавляем HeadA к TailCommonList, получаем CommonList;
    4. возвращаем CommonList и MiscList;
  3. иначе (если HeadA отсутствует во втором списке):
    1. рекурсивно обрабатываем TailA и ListB, получаем CommonList и TailMiscList;
    2. добавляем HeadA к TailMiscList, получаем MiscList;
    3. возвращаем CommonList и MiscList.

Процесс продолжается до тех пор, пока первый список не станет пустым — в этом случае все элементы второго списка переносятся в MiscList.

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

common_misc([], MiscList, [], MiscList):-!.
common_misc([HeadA|TailA], ListB, [HeadA|TailCommonList], MiscList):-
  select(HeadA, ListB, TailB), !,
  common_misc(TailA, TailB, TailCommonList, MiscList).
common_misc([HeadA|TailA], ListB, CommonList, TailMiscList):-
  common_misc(TailA, TailB, TailCommonList, [HeadA|MiscList]).

Тут для поиска элемента с его последующим удалением используется предикат select.

Для поиска общих элементов (пересечения списков/множеств) можно воспользоваться следующим алгоритмом:

intersect([], _B, []):-!.
intersect([HeadA|TailA], B, [HeadA|AInterB]):-
  member(HeadA, B), !,
  intersect(TailA, B, AInterB).
intersect([_HeadA|TailA], B, AInterB):-
  intersect(TailA, B, AInterB).

Мы перебираем последовательно элементы первого множества и выполняем их поиск во втором множестве с помощью предиката member. Если элемент удается найти — то он не должен войти в пересечение, т.е для получения результата достаточно рекурсивно обработать остальные элементы. Если же элемент вход в пересечение, то его нужно добавить к результату, полученному при рекурсивной обработке хвоста. Вычисления заканчиваются (происходит выход из рекурсии) когда первый список оказывается пуст — в этом случае при любом значение второго множества результатом является пустой список.
Исходный код подойдет как для Turbo Prolog, так и для Visual Prolog.