Самая длинная последовательность в Xs, которая состоит из Ys

      Комментарии к записи Самая длинная последовательность в Xs, которая состоит из Ys отключены

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

Помечено: , ,

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

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

    alex007h
    Участник

    Имеется предикат P(Xs,Ys,Zs) ,где Xs,Ys,Zs — списки.

    Задача: Найти самую длинную последовательность в Xs,состоящую из Ys.

    Например
    Xs = [a,b,a,b,c,a,b,d] Ys = [a,b]P([a,b,a,b,c,a,b,d],[a,b],Zs).Zs = [a,b,a,b] % искомый список.

    Буду рад любой помощи, поиск в интернете и по форуму не дал результатов.

  • #2428

    Суть решения может заключаться в том, чтобы составлять все больший список из Ys и пытаться найти его в Xs. Для увеличения длины списка нужно использовать функцию append, выполняющую конкатенацию, а для поиска удобно использовать функцию разделения списка (хотя можно было бы выкрутиться с помощью двух вызовов append).

    Чтобы решение было более оптимальным, необходимо применять хвостовую рекурсию (это будет также эффективно как цикл в императивных языках), а значит — использовать метод накапливающего параметра, заключающийся в том, что результат решения сохраняется в дополнительном аргументе функции. Основная функция поиска решения должна вызывать вспомогательную — содержащую такой аргумент (изначально накапливающий параметр инициализирован пустым списком, т.к. на этом этапе нам не известны более длинные общие подпоследовательности):

    longest_subsequence(List, Part, Subsequence):-
      longest_subsequence_(List, Part, [], Subsequence).

    Вспомогательная функция состоит из двух правил — первое пытается добавить к накапливающему параметру список Ys и найти полученный результат в списке Xs. Если это удается — выполняется рекурсивный вызов с увеличенным накапливающим параметром, иначе — управление передается второму правилу. Второе правило выполняется лишь один раз (т.к. не содержит рекурсивных вызовов) — если увеличить накапливающий параметр уже не удалось. В этом случае ясно, что содержание накапливающего параметра уже является результатом работы функции и его остается лишь вернуть:
    longest_subsequence_(Xs, Ys, CurrentSubsequence, LongestSubsequence):-
      append(CurrentSubsequence, Ys, NextSubsequence),
      divide_list(Xs, [_LeftYs, NextSubsequence, _RightYs]), !,
      longest_subsequence_(Xs, Ys, NextSubsequence, LongestSubsequence).
    longest_subsequence_(_Xs, _Ys, LongestSubsequence, LongestSubsequence).

    Вложения:

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