Задача:: В списке символов S1, S2, …, SN найти первое и последнее вхождения у

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Задача:: В списке символов S1, S2, …, SN найти первое и последнее вхождения у

Помечено: , , , ,

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

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

    arkarkyaw
    Участник

    Задача:

    В списке символов S1, S2, …, SN найти первое и последнее вхождения указанного символа и исключить все символы между ними.

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

  • #4319

    Первое что нужно сделать в этой задаче – найти первое и последнее вхождение заданного символа в списке. Для этого можно сначала найти все вхождения заданного символа и определить их индексы с помощью встроенной функции nth0 и findall:

    findall(Index, nth0(Index, List, Elem), Indecies),

    Затем с помощью встроенных предикатов найти наибольший и наименьший индексы:

    max_list(Indecies, MaxIndex),
    min_list(Indecies, MinIndex), 

    Осталось исключить элементы между MinIndex и MaxIndex, сделать это можно следующим образом:

    crop_list(List, From, To, Crop):-
        CenterLength is To - From + 1,
        divide_list(List, [Left, Center, Right]),
        length(Left, From), length(Center, CenterLength),
        append(Left, Right, Crop).

    Тут мы разбиваем исходный список на 3 части (Left, Center и Right) с помощью функции divide_list. Зная индексы можем определить размер каждой части. Стандартным предикатом append выполняется соединение левой и правой частей – следовательно все элементы между минимум и максимум (Center) будут исключены.

    Для реализации второй задачи можно воспользоваться аналогичным подходом. В приведенном выше решении достаточно вернуть Center вместо результата соединения Left и Right. Однако можно решить задачу более красиво:

    sublist_from_to(List, From, To, Crop):-
        findall(Elem, (between(From, To, Id), nth0(Id, List, Elem)), Crop).

    Функция between выдает по очереди номера элементов между From и To, а функция nth0 – выполняет поиск элемента с таким индексом в списке. Наконец, findall вызывает эли функции и собирает все полученные решения (значения найденных элементов) в список. Этот список и является результатом работы.

    Вложения:

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