Длина наибольшей подпоследовательности из одного символа

      Комментарии к записи Длина наибольшей подпоследовательности из одного символа отключены

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

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

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

    Lucky
    Участник

    Помогите решить задачу на списки, пожалуйста:

    в списке символов S1, S2 , ..., Sn найти длину наибольшей последовательности, построенной повторением одного и того же символа.

  • #2490

    Нужно разделить задачу на части, согласитесь, было бы удобно, если бы у вас была функция, возвращающая последовательность из одного символа, начинающуюся с первого символа строки. Тогда вы могли бы вызвать ее, а затем — рекурсивно обработать список без первого элемента и сравнить результаты:

    longest_symbol_subsequence([], []).
    longest_symbol_subsequence([Head|Tail], LongestSubsequence):-
      first_symbol_subsequence([Head|Tail], FirstSymbolSubsequence),
      longest_symbol_subsequence(Tail, TailSymbolSubsequence),
      length(FirstSymbolSubsequence, LengthFistSymbolSubsequence),
      length(TailSymbolSubsequence, LengthTailSymbolSubsequence),
      (
        LengthFistSymbolSubsequence > LengthTailSymbolSubsequence, !, 
        LongestSubsequence = FirstSymbolSubsequence;
        LongestSubsequence = TailSymbolSubsequence
      ).

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

    first_symbol_subsequence([], []):-!.
    first_symbol_subsequence([Head], [Head]):-!.
    first_symbol_subsequence([Head, Head|Tail], [Head|TailSymbolSubsequence]):-
      !, first_symbol_subsequence([Head|Tail], TailSymbolSubsequence).
    first_symbol_subsequence([Head, _Head2|_Tail], [Head]):-!.

    Определить искомую длину последовательности можно при помощи встроенной функции length.

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