argon bulletin board

Експертно търсене  

Новини:

Регистрирането на нови потребители е временно деактивирано.

Автор Тема: Задачка по ЛФП  (Прочетена 1745 пъти)

ipb

  • Неактивен Неактивен
  • Публикации: 43
Задачка по ЛФП
« -: 04.10.2011, 15:43:28 »

Задачката е:

Дефинирайте предикат, който вмъква 1 пред всеки нулев елемент на даден списък.



Намерил съм темата, в която е обяснено и дори накрая има същата задача като тази, обаче не мога да намеря смисъла в примерите.

Примерно вижте това.Това е обяснение как се трие елемент от списък:
(Написал съм го 1 към 1 от лекциите.)

Цитат
Задача: Изтриване на всяко срещане на елемент А в списък L1 -
del (A, L1, L2)

        Решение:
        del (A, [AlT, L) :- !, del(A, T, L).
        del (A, [BlT], [BlT1]) :- del(A, T, T1).

Какво е del (A, L1, L2)? Това е формулата ли? Това означава да изтрие всички А-та от списъците L1 и L2, така ли?

В решението: Защо се използват опашки (l)? От къде доидоха B, T, T1 и L?

Просто не разбирам какво искат да кажат а по такъв начин са описани всичките задачи и не мога да ги осмисля, за да ги решавам. :-(
Активен

gocev

  • Неактивен Неактивен
  • Публикации: 29
  • Will code .NET for Food.
Re:Задачка по ЛФП
« Отговор #1 -: 04.10.2011, 16:52:37 »

Здрасти.

Да ти поясня какво прави функцията ти дел:

del(Attribute,List,Result)

Където

Attribute - какво се трие.
List - списъка от който се трият елементите.
Result- резултата след изтриване.

Първия ти случай:

del (A, [AlT], L) :- del(A, T, L). Изтрива елемента ако A е глава на опашката първи елемент.

Пример:

искаш да изтриеш буквата о от списъка оасдасдассд.

Тогава се влиза в този случай.

Втория случай:

 del (A, [BlT], [BlT1]) :- del(A, T, T1).

Показва че елемента който трябва да изтриеш не съществува в главата т.е. се намира в опашката.

Също така в задачата има пропуск. Трябва да се започва с del(A,[],[]).

Сега по въпросите ти:

del(A,L1,L2) e функцията за изтриване.

функцията дел(A,L1,L2) изтрива всички елементи от подадения списък L (в твоя случай L1).

Използването на опашка ти гарантира обхождането на списъка.

B != А - глава която не е търсения елемент за изтриване.

T - опашка. Листа представлява двоика от единичен елемент(Head) и всички останали (Tail) [Head|Tail].

Т1- новата опашка която ще се получи при изтриването на елемента от старата опашка T.

L - в случая съхранява резултата ти.

Съжалявам ако има някакви грешки, малко съм ги позабравил нещата. Ако някой колега има забележки приемам критика :)
Активен
(\__/)
(='.'=)
(")_(")

Help Bunny by Copying and pasting him! Help him gain world domination.

ipb

  • Неактивен Неактивен
  • Публикации: 43
Re:Задачка по ЛФП
« Отговор #2 -: 04.10.2011, 18:36:20 »

Значи с първият ред изтривам A от главата на T и резултата е новия списък L.

С втория ред изтривам всички A-та от опашката на Т и резултата е списък T1.
При втория ред се пише "В" в главата, тъй като главата не ни е нужна.

Дотук вярно ли съм го разбрал?  :-)
Мога ли да пиша примерно Х вместо В?


Сега към задачата с добавянето на число.
Мисля че ще се използва нещо от този род, но не съм сигурен:

Цитат
Задача: Сортиране чрез вмъкване – sort (L, S)
Решение:
sort ([], []).
sort ([X|Т], L) :- sort (T, T1), insert (X, T1, L).
insert (X, [H|T], [H|T1]) :- X>H, !, insert (X, T, T1).
insert (X, L, [X|L]).


Активен

gocev

  • Неактивен Неактивен
  • Публикации: 29
  • Will code .NET for Food.
Re:Задачка по ЛФП
« Отговор #3 -: 05.10.2011, 13:30:08 »

Значи с първият ред изтривам A от главата на T и резултата е новия списък L. - с първия ред изтриваш А от head-a и подаваш списъка за доизтриването на останалите елементи.

С втория ред изтривам всички A-та от опашката на Т и резултата е списък T1.
При втория ред се пише "В" в главата, тъй като главата не ни е нужна. - във втория ред виждаш , че елемента го няма в главата и подаваш опашката за доизтриване.

Дотук вярно ли съм го разбрал?  :-) - съответно не :)
Мога ли да пиша примерно Х вместо В? - да разбира е просто трябва да е елемент различен от А.


Сега към задачата с добавянето на число.
Мисля че ще се използва нещо от този род, но не съм сигурен:

Цитат
Задача: Сортиране чрез вмъкване – sort (L, S)
Решение:
sort ([], []).
sort ([X|Т], L) :- sort (T, T1), insert (X, T1, L).
insert (X, [H|T], [H|T1]) :- X>H, !, insert (X, T, T1).
insert (X, L, [X|L]).

силно предполагам че алгоритъма който си дал е INSERT sort а не вмъкване на елемент преди всяка 0 ;)


Активен
(\__/)
(='.'=)
(")_(")

Help Bunny by Copying and pasting him! Help him gain world domination.

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #4 -: 07.10.2011, 10:53:45 »

Направете предикат два параметъра и с три клаузи:
1. Първата е стоп правилото както при del (т.е. това коет липсва в решението) т.е. при празен списък да връща празен спискък, защото в празния списък няма как да има нулев елемент и съответно няма нужда да се вмъква 1-ца никъде;
2. Втората клауза трябва да разглежда случая когато главата на спъсъка първи елемент е 0-ла. Тогава резулата (т.е. втория елемент трябва да е списък с глава съдържаща 1-ца последвана от 0-ла, а опашката на списъка трябва да е резултата от рекурсивно преработената опашка на първия параметър;
3. Третата клауза трябва да разглежда случая когато главата на първия параметър не е 0-ла. Тогава резултата трябва да е списък с глава, главата на първия списък, и опашка аналогично прераотена както опашката в предишно правило (т.е. същата рекурсия).

Е, как това ще изглежда като програма - това е ваша задача. Успех :)
Активен
А.Пенев

ipb

  • Неактивен Неактивен
  • Публикации: 43
Re:Задачка по ЛФП
« Отговор #5 -: 08.10.2011, 22:40:41 »

ins ([], []).
ins([0|T], [1,0|L]) :-  ins (T, L).
ins([X|0], [X|1,0]) :-  ins (T, L).

Така?
Активен

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #6 -: 10.10.2011, 09:34:17 »

Почти да  :-)
Третата клауза не е добре обаче. Тялото и е ОК, но виж T и L ги няма никъде в паралетрите.
И като го оправиш това, помисли (или пробвай) дали няма да има нужда от символа за отсичане "!" някъде (или условие за X да не е 0-ла в третата клауза, въпреки че аз бих използвал символ за отсичане за да се избегнат ненужните преудволетворявания в някои случаи). Огледай пак del-a.
« Последна редакция: 10.10.2011, 09:37:40 от А.Пенев »
Активен
А.Пенев

ipb

  • Неактивен Неактивен
  • Публикации: 43
Re:Задачка по ЛФП
« Отговор #7 -: 11.10.2011, 13:03:39 »

ins ([], []).
ins([0|T], [1,0|L]) :- !, ins (T, L).
ins([T|X], [L|1,X]) :- X=0,  ins (T, L).

Така как е?
Активен

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #8 -: 11.10.2011, 13:16:44 »

Почти идеално  :-)
само че в третото правило нещо си ги омотал променливите, а и проверката за различно от 0-ла няма да е нужна след като имаш отсичане в предишното правило. Според мен трябва да размениш главите и опашките на двата параметъра - [X|T] и [X,L]. Също тази единица не е нужна в случая на третото правило, защото при него няма да вмъкваме нищо в главата на списъка, а просто запазваме този ненулев елемент.
Хайде давай последен опит :-D мисля че вече си на финала и ще успееш да го напишеш добре.
Активен
А.Пенев

ipb

  • Неактивен Неактивен
  • Публикации: 43
Re:Задачка по ЛФП
« Отговор #9 -: 11.10.2011, 14:35:04 »

ins ([], []).
ins([0|T], [1,0|L]) :- !, ins (T, L).
ins([X|T], [X|L]) :- ins (T, L).
Активен

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #10 -: 11.10.2011, 16:49:02 »

 :y: Идеално
Активен
А.Пенев

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #11 -: 11.10.2011, 16:55:29 »

Пробва ли го в някоя среда за Пролог?

Пробвай следните запитвания:
?- ins([1,2,3], X).
?- ins([1,2,1,2], X).
?- ins([], X).
?- ins([2,3,4], X).

и също работата в обратна посока (което е едно от приятните неща на добре написаните програми на Пролог):
?- ins(X, [0,1,2,3]);
?- ins(X, [0,1,2,0,1]);

също:
?- ins([1,2,3], [0,1,2,3]).
?- ins([1,2,3], [1,2,3]).
« Последна редакция: 11.10.2011, 17:22:33 от А.Пенев »
Активен
А.Пенев

ipb

  • Неактивен Неактивен
  • Публикации: 43
Re:Задачка по ЛФП
« Отговор #12 -: 11.10.2011, 18:08:23 »

Не съм.Всичко го гледам от лекциите и от каквото съм записал.

Дотук добре.

Втора задача. :-D

Дефинирайте предикат, който по даден списък от числа [a1, a2, a3, a4, ...], пресмята сумата: a1.(a2+1)+a3.(a4+1)+ ...

Така вярно ли е:

sum([],0):- !.
sum([_],0):- !.
sum([X,Y|T],S):- sum(T,S1), S is S1+X*(Y+1).
Активен

А.Пенев

  • Неактивен Неактивен
  • Публикации: 157
    • www.alexander-penev.info
Re:Задачка по ЛФП
« Отговор #13 -: 11.10.2011, 18:19:54 »

Да
Активен
А.Пенев