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

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

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

#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.