Выбрать из списка элементы, меньше своих соседей

      Комментарии к записи Выбрать из списка элементы, меньше своих соседей отключены

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

Помечено: ,

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

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

    questioner
    Участник

    На языке Prolog нужно написать программу, которая из списка выберет элементы, значения которых меньше значений соседей. Мной написан следующий код:

    pit([], []).
    pit([_], []).
    pit([X, Y], L):- 
      X > Y, !, L = [Y]; 
      L = [].
    pit([X, Y, Z|L], R1):-  
      pit([Y,Z|L], R), 
      (
        Y < X, Y < Z, !, R1 = [Y|R]; 
        R1 = R
      ).

    Не работает если первый элемент меньше второго.
    Примеры корректных входных и выходных данных:
    ?- pit([3,2,5], X).
    X = [2].
    ?- pit([1,2], X).
    X = [1].
    ?- pit([1,8,2,3,5,3], X).
    X = [1,2,3].

  • #3189

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

    Основную часть алгоритма я записал следующим образом:

    pit([], []):-!.
    pit([_], []):-!.
    pit(From, Pits):-
      pit_first(From, HeadPits),
      pit_middle(From, MiddlePits),
      pit_last(From, LastPits),
      append(HeadPits, MiddlePits, Part),
      append(Part, LastPits, Pits).

    Я вызывают три разных функции для обработки начала, конца и середины, результаты соединяю с помощью append.

    При обработке первого элемента я должен лишь сравнить его значение со вторым элементом:

    pit_first([A, B|_Tail], [A]):-
      A < B, !.
    pit_first(_List, []).

    Чтобы обработать последний элемент, мне надо сначала добраться до него — я продолжаю отбрасываться элементы из начала списка до тех пор, пока не останется два элемента в списке, а затем выполняю сравнение:

    pit_last([A, B], [B]):-
      B < A, !.
    pit_last([_A, _B], []):-!.
    pit_last([_A, B|Tail], Pits):-
      pit_last([B|Tail], Pits).

    Обработка элементов из середины списка происходит подобно тому, как это делалось в вашем коде. Я беру элементы тройками, проверяю чтобы второй был больше остальных, отбрасываю первый элемент, а остальные обрабатываю рекурсивно:

    pit_middle([_A, _B], []):-!.
    pit_middle([A, B, C|Tail], [B|PitsTail]):-
      B < A, B < C, !,
      pit_middle([B, C|Tail], PitsTail).
    pit_middle([_A, B, C|Tail], PitsTail):-
      pit_middle([B, C|Tail], PitsTail).

    Результаты работы программы:
    prolog-lists-pits

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