Обратить отрезок из m элементов, следующих за k-ым элементом данного списка

      Комментарии к записи Обратить отрезок из m элементов, следующих за k-ым элементом данного списка отключены

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

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

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

    questioner
    Участник

    Помогите, пожалуйста. На Visual Prolog обратить отрезок из m элементов, следующих за k-ым элементом данного списка l. За один проход по списку.
    l — список, элементами которого являются списки.
    Списки из обращенного отрезка не обращать.

    Есть вот такое решение, но преподаватель сказал, что это функциональный стиль, так не подойдет (тут не за один проход):

    domains
      l=integer*
      ll=l*
     
    predicates
      nondeterm append(ll,ll,ll)
      %первый список склеивает со вторым и результат выдает в третьем
      %списке.
      nondeterm revL(integer,integer,ll,ll)
      %первое число –это k,второе число –m,кол-во переворачиваемых
      %элементов.затем исходный список. последний аргумент- результат.
      nondeterm p(integer,ll,ll,ll)
      %первое число-k.первый список –исходный. второй список содержит
      %элементы от начала до k.третий список содержит элементы от k+1
      %до конца.
      nondeterm reverse(ll,ll)
      %обращает первый список. второй-результат.
    clauses
      append([],L,L):-!.
      append([H|T],L,[H|T1]):-
        append(T,L,T1).
      
      revL(K,M,L0,L):-
        p(K,L0,L1,X), p(M,X,L2,L3),
        reverse(L2,LL2),
        append(L1,LL2,Y), append(Y,L3,L).
     
      p(0,L,[],L):-!.
      p(N,[H|T],[H|T1],L):-
        N1=N-1, p(N1,T,T1,L).
     
      reverse([X],[X]):-!.
      reverse([H|T],L):-
        reverse(T,T1), append(T1,[H],L).
     
    goal
      revL(1,2,[[1,2,3],[4,5],[6,7,8],[9]],L).

  • #1884

    Приведенный Вами код имеет линейную асимптотическую сложность, т.е. это тоже самое, что «каждый элемент обрабатывается один раз». Нет по сути разницы один раз или 2 раза, главное что не M раз.

    Я считаю, что правильное решение — разбить исходный список на 3 части — из K элементов, из M элементов и всех остальных элементов. Вторую часть перевернуть и слить все в кучу. Если список содержит Len элементов, то разбиение выполнится за O(Len), переворот — за О(M), слияние — за O(K + M). Верхняя оценка O(Len). Придумать более оптимальный алгоритм не выйдет.

    Я думаю, что преподаватель ждет что-то такое (хотя это ничем не лучше):

    %% обратить отрезок из M элементов, следующим за K-тым элементом списка L
    %%p(K, M, L, R)
    p(K, M, L, R):-
        p(K, M, L, [], R).
     
    %%p(K, M, L, TR, R)
    p(_, _, [], TR, TR):-!.
    p(_, 0, L, TR, R):-
        append(TR, L, R),!.
    p(0, M, [H|T], TR, R):-
        !, MM is M - 1, p(0, MM, T, [H|TR], R).
    p(K, M, [H|T], TR, [H|TTR]):-
        !, KK is K - 1, p(KK, M, T, TR, TTR).

    Комментарии к коду по строкам:
    7) если исходный список пуст, то вернуть надо то, что накопилось в буфере (TR). Эта строчка выполнится если длина списка меньше чем K + M;
    8) если M равно нулю, то переворачивать ничего не надо. Надо вернуть исходный список (L), но нельзя забывать, что что-то накопилось в буфере (TR) — требуется соединить буфер с необработанной частью списка. Если преподавателю не понравится append — то этот кусочек можно переписать вручную, но лично я смысла не вижу в этом. Гарантирую, что код будет читаться хуже, а одна из особенностей логического программирования — простота восприятия кода;
    10) если K равно нулю, то переворачивать надо, начиная с первого элемента списка, а для этого первый элемент помещается в буфер. Элемент помещается в начало буфера, поэтому первый помещенный в буфер элемент окажется в конце, а последний — в начале, т.е. так и получится осуществить переворот части списка;
    12) предыдущие правила не сработали, значит ни M, ни K не равны нулю, поэтому надо продолжать извлекать элементы из начала уменьшая K.

    Ни приведенный мной тут код, ни вариант уже отклоненный преподавателем не являются оптимальными. Правильное решение должно использовать хвостовую рекурсию. У меня в 12 строке результат формируется после того, как будет завершено выполнение функции, вызываемой рекурсивно, при этом к результату функции прикрепляется элемент H. Пока вызываемая функция вычисляется элемент H хранится в стеке, а если список длинный — стек переполнится. В вашем варианте тоже используется стек.

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

    Правило может быть не золотое, если проектируется космический корабль и работает целый НИИ — то оно явно не используется, но все требования в этих случаях все равно адекватны и выражены формально.

    Про золотое правило можно прочитать в книге Томпсона про Erlang.

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