Задачи за самостоятелна подготовка

Почти палиндром

Почти палиндром

от Трифон Трифонов -
Number of replies: 9

(Това е задача, давана миналата година на контролно по ПРОЛОГ). Списък се нарича почти палиндром, ако

а) при промяната на точно един негов елемент с друг, (различен от него) се получава списък, който е палиндром;
б) при изтриването на точно един негов елемент, се получава списък, който е палиндром.

Палиндром е списък, който се чете по-един и същ начин отпред назад и отзад напред.

Напишете предикат almost_paly(L), който проверява дали даден списък е почти палиндром. Внимание: не всеки палиндром е почти палиндром, но някои са.

In reply to Трифон Трифонов

Re: Почти палиндром

от Nadia Robakova -

is_ap(L):-reverse(L,L1),L=L1,!,len(L,X),X mod 2=:=1.

is_ap(L):-reverse(L,L1),len(L,Len),mid(L,L2,Len),mid(L1,L3,Len),        is_ap2(L2,L3).

len([],0):-!.

len([H|T],X):-len(T,X1),X is X1+1.

mid([X],[X],L).

mid([H|T],[H|T1],X):-len(T,X1),X <(X1+1)//2,mid(T,T1,X).

is_ap2([H|T],[H|T1]):-!,is_ap2(T,T1).

is_ap2([H|T],[H1|T1]):-T=T1.

In reply to Nadia Robakova

Re: Почти палиндром

от Трифон Трифонов -

Здравей, Надя,
  идеята ти е добра, но предикатът mid не е вярно написан. Много хитра е реализацията на is_ap2. Опитай се за упражнение да я направиш и без cut.

Трифон

In reply to Трифон Трифонов

Re: Почти палиндром

от Nadia Robakova -

 A taka stava li?

mid([H|T],[H|T1],X):- len(T,X1),X2 is X-X1,X1<X2,mid(T,T1,X).

Bez parvata proverka.

In reply to Nadia Robakova

Re: Почти палиндром

от Трифон Трифонов -
Не, и така не е добре. Нямаш ли ПРОЛОГ да тестваш? Проблемът е по-скоро в дъното на рекурсията. Така резултатът ти става точно толкова дълъг, колкото и списъка, който подаваш като първи параметър. Ако проверката се провали само ще получиш No още на mid, независимо от проверката на is_ap2.
In reply to Трифон Трифонов

Re: Почти палиндром

от Боян Табаков -
Не трябва ли дъното на mid да е следното:
mid([X], [X], 1).
In reply to Трифон Трифонов

Re: Почти палиндром

от Боян Табаков -
Решение на а) (малко дългичко ми излезе, но предикатите get_first и diff_count са по-универсални от необходимостта на конкретната задача):

%:: BEGIN CODE::
%допълнителни предикати
append([], B, B).
append([H|T], B, [H|C]):-append(T, B, C).

reverse([], []):-!.
reverse([H|T], R):-reverse(T, T1), append(T1, [H], R).

%ясно какво прави :)
length([], 0):-!.
length([_|T], L):-length(T, L1), L is L1 + 1.

%връща във втория си аргумент първите C елемента на първия списък
get_first([], [], _):-!.
get_first(_, [], 0):-!.
get_first([H|T], [H|R], C):-C>0, C1 is C - 1, get_first(T, R, C1).

%брои в колко позиции се различават два списъка
%ако те са с различна дължина, всички позиции в повече
%се броят за различни
diff_count([], L, C):-!, length(L, C).
diff_count(L, [], C):-!, length(L, C).
diff_count([H|T1], [H|T2], C):-!, diff_count(T1, T2, C).
diff_count([_|T1], [_|T2], C):-diff_count(T1, T2, C1), C is C1 + 1.

a_pal_mod([]):-!.
a_pal_mod(L):-reverse(L, L), !, length(L, Len), Len mod 2 =:= 1.
a_pal_mod(L):-length(L, Len), Half is Len // 2,
reverse(L, L1), get_first(L, N, Half), get_first(L1, M, Half),
diff_count(N, M, 1).
%::END CODE::

В листовете, които имам в б) се иска при ДОБАВЯНЕ на произволен елемент на произволно място да се получи палиндром...
Иначе само с изтриване става доста лесно - само един генератор на списък, в който липсва един от елементите му...

%::BEGIN CODE::
%генерира списъка с добавен Х на произволно място
insert_gen(X, [], [X]):-!.
insert_gen(X, [H|T], [X|[H|T]]).
insert_gen(X, [H|T], [H|R]):-insert_gen(X, T, R).

%генерира елементите на списъка последователно
at_gen([H|_], H).
at_gen([_|T], X):-at_gen(T, X).

a_pal_ins(L):-reverse(L, L), !.
a_pal_ins(L):-at_gen(L, X), insert_gen(X, L, R), reverse(R, R).
%::END CODE::

Някакви забележки?
In reply to Боян Табаков

Re: Почти палиндром

от Трифон Трифонов -
Здравей,
  решението на а) е вярно, предполагам и ти си го тествал. Решението на б) също е вярно, всъщност решенията за добавяне и изтриване на елемент стават лесно и не се различават особено много. Забележи, че at_gen е всъщност member.
  В интерес на истината а) също може да се направи в стила на б). Идеята е, че има смисъл да променяш даден елемент само ако го промениш на друг елемент от списъка. Така ако генерираш всички възможни подмени с всички възможни елементи от списъка, все ще получиш палиндром, ако списъкът ти е почти палиндром :)
In reply to Трифон Трифонов

Re: Почти палиндром

от Боян Табаков -
За решението на а) като б) се сетих, но вече бях написал итеративното решение, което ще е по-бързо при всички положения (знам, че не гоним ефективност, но все паксмях).
Иначе за at_gen - нямах написан member, а at_gen беше първото име, което ми хрумна - но са си еднакви...