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

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

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

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

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

    Anubis
    Участник

    Составить программу, которая образует два списка: список общих элементов и список различных элементов для двух данных списков. Элементы в исходных списках не должны повторяться.
    Входные списки должны вводится с клавиатуры.
    Решить нужно на 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.

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