Deklaratív programozás 3. Prolog gyakorlat 2024 október 29. Prolog programozás: listák, egyklózos megoldások ---------------------------------------------------------------- 1. Beszúrás rendezett listába % insert_ord(+RL0, +Elem, ?RL): Az RL szigorúan monoton növő % egészlista úgy áll elő, hogy az RL0 szigorúan növő egészlistába % beszúrjuk az Elem egész számot, feltéve hogy Elem nem eleme az % RL0 listának; egyébként RL = RL0. Megoldása legyen % jobbrekurzív, ne hagyjon választási pontot, használjon % feltételes szerkezetet! | ?- 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 Megvalósítási ötletek: - A predikátum két klózból álljon: az elsõ az üres lista, a második a nem-üres lista esetét fedje le. - A második klózban egy feltételes szerkezet segítségével ágazzon el háromfelé aszerint hogy RL0 feje és Elem milyen viszonyban van: <, =, vagy >. A jobbrekurzió érdekében az RL kimenõ argumentumot behelyettesítõ hívást hozza a rekurzív hívás elé. --------------------------------------------------------------------------- Otthoni, szorgalmi feladat: oldja meg ugyanezt a feladatot vágó használatával (feltételes szerkezet és diszjunkció nélkül), úgy hogy csak három klózból álljon a predikátum. % insert_ord_1(+RL0, +Elem, ?RL): ugyanaz mint az % insert_ord(+RL0, +Elem, ?RL), csak a vágó % beépített eljárás használatával. 2. Két rendezett egészlista összefésülése egy rendezett listává % merge(+RL0, +RL1, ?RL): RL0 és RL1 szigorúan rendezett listák % összefésülése egy szigorúan rendezett RL lista. | ?- merge([1,2],[2,3,4], L). L = [1,2,3,4] ? yes | ?- merge([1,2,3,4],[2,3,4], L). L = [1,2,3,4] ? ; no | ?- merge([1,4,16,64],[2,4,8,16,32], L). L = [1,2,4,8,16,32,64] ? ; no 3. Unalmas listák A 260. előadásdián szerepel az unalmas/2 predikátum: % unalmas(Lista, X): Lista minden eleme = X unalmas([], _X). unalmas([H|T], X) :- H = X, unalmas(T, X). Írjon egy nemrekurzív unalmas1/2 eljárást, amely ekvivalens a fentivel! Használja az append/3 beépített eljárást! Írjon egy szintén nemrekurzív unalmas2/2 eljárást, amely a \+ /2 (nem bizonyítható) beépített eljárásra épül! Mik azok a bemenetek, amikre az unalmas2/2 nem úgy működik mint az unalmas/2 és az unalmas1/2? Az unalmas1/2 és unalmas2/2 eljárásokat "egyklózos" eljárásoknak hívjuk. Ezektől elvárjuk, hogy egyetlen klózból álljanak és ne legyenek rekurzívak, viszont nem várjuk el, hogy hatékonyak legyenek. --------------------------------------------------------------------------- Platónak hívunk egy olyan legalább kételemű listát, amely csupa azonos elemből áll. Az mondjuk, hogy MP egy L listában található maximális plató, ha - MP az L folytonos része (azaz MP előáll úgy, hogy L elejéről és végéről 0 vagy több elemet elhagyunk), - MP egy plató és - MP maximális L-ben, azaz nem lehet sem balra sem jobbra a benne levőkkel azonos, közvetlenül szomszédos elemekkel kiterjeszteni. Például az L = [a.b,a,c,c,c,b,b] listában két maximális plató van, a 4. pozición kezdődő [c,c,c] és a 7. pozición kezdődő [b,b] lista (a listaelemeket 1-től számozzuk). --------------------------------------------------------------------------- 4. Platók felsorolása Írja meg az alábbi fejkommentnek megfelelő plato0/4 egyklózos eljárást, amellyel egy adott listában előforduló platók adatait tudjuk felsorolni. Segítségül megadtuk az eljárás fejéhez és törzséhez tartozó kommenteket. Használja az append/2 és last/2 eljárásokat a lists könyvtárból! plato0(L, I, Len, X) :- % Az L listában az I. pozición van egy % Len hosszúságú, X elemekből képzett % maximális plató HA % L2 két azonos X elemmel kezdődő lista ÉS % L szétszedhető L1, L2, L3 részlistákra ÉS % L2 minden eleme azonos X-szel ÉS % L3 nem X-szel kezdődő lista ÉS % L1 nem X-szel végződő lista ÉS % L2 hossza Len, ÉS % I = (L1 hossza)+1 A következő két eljárás segítségével a fenti plato0/4 eljárással ekvivalens, de lényegesen hatékonyabb plato/4 predikátumot valósítunk majd meg. 5. Kezdő plató Írjon Prolog eljárást amely a bemenetként kezdődő listáról eldönti, hogy egy platóval kezdődik-e, és ha igen, visszaadja a kezdeti plató hosszát és az ezutáni (maradék) elemek listáját. Segédeljárásokat is meg kell valósítania. % pl_kezdetu(L, Len, M): Az atomokból álló L lista egy Len hosszúságú % maximális platóval kezdődik, amelyet az M maradéklista követ. | ?- pl_kezdetu([a,b,a,c,c,c,b,b], Len, M). no | ?- pl_kezdetu([c,c,c,b,b], Len, M). Len = 3, M = [b,b] ? ; no | ?- pl_kezdetu([b,b], Len, M). Len = 2, M = [] ? ; no | ?- pl_kezdetu([b], Len, M). no | ?- pl_kezdetu([], Len, M). no | ?- 6. Hatékony platókeresés Írjon olyan hatékony Prolog eljárást, amely felsorolja atomok egy adott listájában található maximális platókat, megadva a plató hosszát és az ismétlődő elemet. Használja a pl_kezdetu/3 eljárást! % plato(+L, ?Len, ?X): Az L listában található egy Len hosszúságú, % X elemekből képzett maximális plató. | ?- plato([a,b,b,b,b,a,a,c,b,b], Len, X). Len = 4, X = b ? ; Len = 2, X = a ? ; Len = 2, X = b ? ; no 7. Futamok Egy olyan listát, amelyekben sokszor ismétlődnek a szomszédos elemek, érdemes lehet tömörítve tárolni. Ennek egy formája a futamokkal való ábrázolás, pl.: [a,a,b,c,c,c,c,d,e,e,e,f,f,f] ---> [a-2,b-1,c-4,d-1,e-3,f-3] Tehát az azonos (X) elemekből álló maximális (N) hosszúságú sorozatokat egy X-N párral ábrázolunk a futamok listájában. Írjon egy futamok0/2 Prolog eljárást, amely egy tetszőleges tömör Prolog listát átalakít futamok listájává! (Egy Prolog kifejezés tömör, ha nem tartalmaz változót, vö. a ground/1 beépített eljárással.) | ?- futamok0([a,a,b,c,c,c,c,d,e,e,e,f,f,f], Futamok). Futamok = [a-2,b-1,c-4,d-1,e-3,f-3] ? ; no | ?- futamok0([a,a,a,a], Futamok). Futamok = [a-4] ? ; no | ?- futamok0([a,b,c,d], Futamok). Futamok = [a-1,b-1,c-1,d-1] ? ; no | ?- futamok0([a,b,b,c,a,a,c], Futamok). Futamok = [a-1,b-2,c-1,a-2,c-1] ? ; no | ?- futamok0([], Futamok). Futamok = [] ? ; no Írjon egy komatuf/2 Prolog eljárást, amely egy tetszőleges tömör (azaz változót nem tartalmazó) futamlistát visszaalakít közönséges listává! | ?- komatuf([a-1,b-2,c-1,a-2,c-1], L). L = [a,b,b,c,a,a,c] ? ; no | ?- komatuf([d-1,a-2,d-1], L). L = [d,a,a,d] ? ; no | ?- komatuf([], L). L = [] ? ; no Végül írjon egy futamok/2 Prolog eljárást, amelyik ugyanazt a relációt valósítja meg mint a futamok0/2 eljárás, de mindkét irányban működik: ha az első argumentuma tömör lista, akkor ennek futamlista megfelelőjét egyesíti a második argumentummal; ha a második argumentuma egy tömör futamlista, akkor azt közönséges listává alakítja, és az első argumentumban adja vissza! Ha egyik argumentum sem tömör, az eljárás hiúsuljon meg! | ?- futamok([a,b,b,c,a,a,c], Futamok). Futamok = [a-1,b-2,c-1,a-2,c-1] ? ; no | ?- futamok(L, [a-1,b-2,a-1]). L = [a,b,b,a] ? ; no | ?- futamok([a,X,b,c], Y). no