Deklaratív Programozás gyakorlat Prolog programozás: listák, feltételes szerkezetek használata 2010.03.03. --------------------------------------------------------------------------- --------------------------------------------------------------------------- Írjon olyan Prolog eljárást, amely megfelel az adott fejkommentnek. A feladat megoldásához felhasználhat korábbi sorszámú feladatokban definiált eljárásokat. A fejkommentekben az input-output módok jelölésére használt jelek magyarázata: +: az argumentum bemenő, nem lehet változó (és nem is tartalmazhat változót); -: az argumentum kimenő, azaz változó; ?: az argumentum lehet kimenő és bemenő is. --------------------------------------------------------------------------- 1. Beszúrás rendezett listába % insert_ord(+RL0, +Elem, RL): Az RL monoton növő számlista úgy áll % elő, hogy az RL0 szigorúan növő számlistába beszúrjuk az Elem számot, % feltéve hogy Elem nem eleme az RL0 listának; egyébként RL = RL0. | ?- insert_ord([1,3,5,8], 6, L). L = [1,3,5,6,8] ? ; no | ?- insert_ord([1,3,5,8], 3, L). L = [1,3,5,8] ? ; no Használjon feltételes szerkezetet! 2. Lista adott sorszámú eleme % nth1_1(+N, ?L, ?E): Az L lista N. eleme E (1-től számozva az % elemeket). Az eljárás nevében szereplő első 1-es arra utal, hogy 1-től számozzuk az elemeket, a második egyes pedig arra, hogy ez az első változata egy feladatsornak. | ?- nth1_1(3, [a,b,c], E). E = c ? ; no | ?- nth1_1(3, L, E). L = [_A,_B,E|_C] ? ; no 3. Adott lista sorszámozott eleme % nth1_2(?N, +L, ?E): Az L lista N. eleme E (1-től számozva az % elemeket). | ?- nth1_2(N, [a,b,c], E). E = a, N = 1 ? ; E = b, N = 2 ? ; E = c, N = 3 ? ; % no 4. Lista adott hosszú prefixuma Egy L n-elemű lista prefixumának nevezünk egy listát, ha az az L első k elemét tartalmazza (az L-beli sorrend megtartásával), ahol 0 =< k =< n. % prefix_length(+Whole, ?Prefix, +Length): A Whole lista prefixuma a % Prefix lista, amelynek hossza Length. | ?- prefix_length([a,b,c,d,e], Prefix, 3). Prefix = [a,b,c] ? ; no 5. Lista adott helyen kezdődő szuffixuma Egy L n-elemű lista szuffixumának nevezünk egy listát, ha az az L utolsó k elemét tartalmazza (az L-beli sorrend megtartásával), ahol 0 =< k =< n. % suffix_before(+Whole, ?Suffix, +Before): A Whole lista azon szuffixuma a % Suffix lista, amelyet megelőző elemek száma Before. | ?- suffix_before([a,b,c,d,e], Suffix, 3). Suffix = [d,e] ? ; no 6. Részlista képzése % sublist(+Whole, ?Part, +Before, +Length): A Whole lista azon % (folytonos) részlistája Part, amely előtt Before számú elem áll és % amelynek hossza Length. | ?- sublist([a,b,c,d,e], Part, 1, 3). Part = [b,c,d] ? ; no 7. Részlisták felsorolása % sublist(+Whole, ?Part, ?Before, ?Length, ?After): A Whole lista olyan % (folytonos) részlistája Part, amely előtt Before és amely után After % számú elem áll, és amelynek hossza Length. | ?- sublist([a,b], Part, Before, Length, After). Part = [], After = 2, Before = 0, Length = 0 ? ; Part = [a], After = 1, Before = 0, Length = 1 ? ; Part = [a,b], After = 0, Before = 0, Length = 2 ? ; Part = [], After = 1, Before = 1, Length = 0 ? ; Part = [b], After = 0, Before = 1, Length = 1 ? ; Part = [], After = 0, Before = 2, Length = 0 ? ; no =========================================================================== Szorgalmi/otthoni feladatok =========================================================================== 8. Lista sorszámozott eleme: több irányban működő eljárás Gondolja meg, hogy mennyire hatékony a 3. feladatra adott megoldása abban az esetben ha N egy adott szám. A var/1 beépített eljárás és feltételes szerkezet használatával készítse el a (2, és 3. feladatbeli) nth1_1 és nth1_2 eljárások egy olyan nth1_3 kombinációját, amely minden input-output módban helyesen és hatékonyan működik (ha az első két argumentum behelyettesítetlen, akkor -- jogosan -- végtelen sok megoldást adjon vissza). 9. Beszúrás listába adott helyre % insert_nth(+N, ?L0, ?E, ?L): Az L lista N. eleme E, ezt megelőző % elemei azonosak L0 1., 2., ... N-1. elemével, ezt követő elemei % azonosak L0 N., N+1., ... elemeivel. | ?- insert_nth(3, [a,b,c,d,e], i, L). L = [a,b,i,c,d,e] ? ; no | ?- insert_nth(3, [a,b,c,d,e], X, L). L = [a,b,X,c,d,e] ? ; no | ?- insert_nth(3, [1], 2, L). no | ?- insert_nth(3, L0, X, L). % (*) L = [_A,_B,X|_C], L0 = [_A,_B|_C] ? ; no Oldja meg a feladatot feltételes szerkezet használatával is (a megoldásban az utóbbi insert_nth_2 néven szerepel). 10. Beszúrás adott listába % insert_nth_3(?N, +L0, ?E, ?L): Az L lista N. eleme E, ezt megelőző % elemei azonosak L0 1., 2., ... N-1. elemével, ezt követő elemei % azonosak L0 N., N+1., ... elemeivel. Az insert_nth_2 eljárás ugyanazt az eredményt adja mint az insert_nth az utóbbinál felsorolt példák esetén, kivéve a (*)-gal jelöltet, és müködik az alábbi példákra is: | ?- insert_nth_3(N, [1], 2, L). L = [2,1], N = 1 ? ; L = [1,2], N = 2 ? ; no | ?- insert_nth_3(N, [1], X, L). L = [X,1], N = 1 ? ; L = [1,X], N = 2 ? ; no Ezt a feladatot kihagyhatja ha helyette megoldja az alábbi 11. feladatot, amely ennek egy általánosítása. 11. Beszúrás adott listába vagy adott lista-eredménnyel Az insert_nth_4 eljárás jelentése (és fejkommentje) ugyanaz mint az 9. és 10. feladatbeli eljárásé, de működnie kell akkor is, ha meg van adva az a lista, amelybe beszúrunk, és akkor is ha a beszúrás eredménye adott: :- mode insert_nth_4(?, +, ?, ?). :- mode insert_nth_4(?, -, ?, +). A 9. és 10. feladatokban felsorolt összes példa esetén a megadott eredményt adja, kivéve a (*)-gal jelöltet, és müködik az alábbi példára is: | ?- insert_nth_4(N, L0, X, [a,b]). N = 1, X = a, L0 = [b] ? ; N = 2, X = b, L0 = [a] ? ; no Vizsgálja meg, hogy mennyire hatékony ez a megoldás abban az esetben ha N egy megadott szám. A var/1 beépített eljárás és feltételes szerkezet használatával készítsen egy olyan insert_nth/4 változatot, amely hatékonyan működik ha az 1., 2. és 4. argumentumok közül legalább az egyik adott (szám ill. zárt végű lista). A megoldásban ez a változat insert_nth_5 néven szerepel. =========================================================================== Tippek: 3. feladat A member/2 eljárás két argumentumát cserélje meg, és egészítse ki egy első N argumentummal, amely a beszúrás helyét számlálja. Mivel N lehet behelyettesítetlen változó is, ezért tekintse kimenő argumentumnak. (Nem baj, ha az eljárás nem jobbrekurzív.) 10. feladat A select/3 eljárás argumentumainak átrendezesével készítsen egy insert/3 ejárást: % insert(L0, E, L): L az L0 listából az E elem beszúrásával jön létre. Ezt az eljárást egészítse ki egy N első argumentummal, és kövesse a 3. feladathoz adott tippet.