N последних элементов исходного списка

      Комментарии к записи N последних элементов исходного списка отключены

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

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

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

    Решим на языке Prolog задачу:

    Подсписок из N последних элементов исходного списка, в том же порядке.

    Первый вариант решения может заключаться в использовании встроенных функций для разделения списка на части и получения длины списка:

    last_elements(List, N, Last):-
      append(_LeftPart, Last, List), length(List, N).

    Тут мы говорим, что исходный список состоит из двух частей, при этом первая часть нас не интересует, а у второй – длина равна N. Это решение хорошо сработает например в SWI Prolog, однако в Visual Prolog нет встроенного предиката append. Наша реализация (см. в статье “Обработка списков в Prolog“) этого предиката позволяет соединять два списка, но не выполнять разделение списка на части.

    Решение для Visual Prolog может выглядеть так:

    domains 
    	list = integer*
    predicates
      	last_elements(list, integer, list) 
      	last_elements(list, integer, integer, list) 
    clauses	
      	last_elements(List, SublistLength, Sublist):-
      		last_elements(List, _EndPos, SublistLength, Sublist).
      		
      	last_elements([], 0, SublistLength, []):-!.
      	last_elements([Head|Tail], EndPos, SublistLength, Sublist):-
      		last_elements(Tail, TailEndPos, SublistLength, SublistTail),
      		TailEndPos >= SublistLength, !, 
      		Sublist = SublistTail, EndPos = TailEndPos + 1.
      	last_elements([Head|Tail], EndPos, SublistLength, Sublist):-
      		last_elements(Tail, TailEndPos, SublistLength, SublistTail),
      		TailEndPos < SublistLength, !, 
      		Sublist = [Head|SublistTail], EndPos = TailEndPos + 1.	
    goal
      	last_elements([1,2,3,4,5,6,7,8,9], 4, X).

    last_elements

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

    1. достигнув конца списка вернет пустой список (в качестве последних N элементов) и ноль в качестве позиции текущего элемента в списке;
    2. в результате рекурсивного вызова получит TailEndPos — позицию (считая от конца) списка первого элемента Tail и подсписок, сформированный при обработке хвоста;
    3. если TailEndPos больше требуемой длины подсписка, то первый элемент (Head) к результату добавлять не требуется — поэтому функция лишь увеличивает позицию элемента, но не изменяет полученный подсписков;
    4. если же TailEndPos < SublistLength, то не только увеличивается позиция элемента, но и первый элемент дописывается к результату.

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