Alkalmazott Funkcionális és Logikai Programozás Prolog programozási gyakorlat 2012. 10. 11. --------------------------------------------------------------------------- "A" Témakör: a Prolog alapelemei: szintaxis, szemantika (végrehajtás) Írja fel az alábbi egyenlõségek bal- és jobboldalának alapstruktúra alakját, vagy rajzolja fel a fastruktúrájukat! Adja meg, milyen változó- behelyettesítéseket eredményeznek ezek az egyesítések! A1. [a*b-X,c+X] = [Y-3|Z]. A2. g(V*W, [1*2+3|Z]) = g(K, [K+L,L]). A3. (szorgalmi, otthoni feladat) s([a]-X/2, [X|Z]) = s(Z-Y, [f,C]). A4. (szorgalmi, otthoni feladat) [A+B, C*2|T] = .(x/C+2, [y*B, B-C]). "P". Témakör: programok írása A programozási feladatok megoldásaként olyan Prolog eljárást kell írnia, amely megfelel az adott fejkommentnek. Ha külön nem kérjük, akkor nem szükséges, hogy jobbrekurzív (iteratív) eljárásokat írjon, de természetesen a jobbrekurzív változatot ilyenkor is elfogadjuk. Bármely feladat megoldásához felhasználhat korábbi sorszámú feladatokban definiált eljárásokat. Ha ilyeneken kívül is szükséges segédeljárás definiálása, azt külön jelezzük. Természetesen más esetben is használhat segédeljárást. Minden segédeljáráshoz írjon fejkommentet! Nem használhat könyvtári eljárásokat, mellékhatásos beépített eljárásokat, valamint az alábbi listakezelõ eljárásokat: append/3, member/2, memberchk/2, nonmember/2. Hibakezeléssel nem kell foglalkoznia: a megírt eljárásoknak csak a fejkomment által megadott argumentumértékek esetén kell az elõírt módon viselkedniük. Az alábbi példasorban a (bináris) fa adatstruktúra alatt egy olyan Prolog kifejezést értünk, amely lehet - levél, azaz egy `leaf' nevû struktúra, amelynek egyetlen argumentuma egy egész szám, pl. leaf(1), leaf(2); vagy - csomópont, azaz egy node nevû kétargumentumú struktúra, amelynek mindkét argumentuma `fa', pl. node(leaf(1),leaf(2)). A fejkommentekben használt ún. input/output módjelölések magyarázata: *: az argumentum tömör bemenõ, azaz nem lehet változó, és nem is tartalmazhat változót; +: az argumentum bemenõ, azaz nem lehet változó, de tartalmazhat változót (természetesen csak akkor, ha az argumentum egy struktúra); -: az argumentum kimenõ, azaz változó; ?: az argumentum lehet kimenõ és bemenõ is. 1. Számsorozat generálása % seq(+N, +M, -L): Az L lista M-N+1 hosszú, elemei 1 különbségû számtani % sorozatot alkotnak, és L elsõ eleme (ha van) N, ahol N és M egész számok. | ?- seq(2, 4, L). L = [2,3,4] ? ; no | ?- seq(4, 2, L). no | ?- seq(4, 3, L). L = [] ? ; no | ?- seq(-4, -2, L). L = [-4,-3,-2] ? ; no 2. Fa csomópontjainak megszámolása Egy fa csomópontjainak száma a benne elõforduló node/2 struktúrák száma. % fa_pontszama(*Fa, -N): A Fa bináris fa csomópontjainak száma N. | ?- fa_pontszama(node(leaf(1),node(leaf(2),leaf(3))), N). N = 2 ? ; no | ?- fa_pontszama(node(leaf(1),node(leaf(2),node(leaf(4),leaf(3)))), N). N = 3 ? ; no 2. Hatványozás % hatv(+A, +E, -H): H = A ^ E, ahol A egész szám, E >= 0 egész szám. | ?- hatv(3, 5, X). X = 243 ? ; no 3. Fa minden levélértékének növelése % fa_noveltje(*Fa0, ?Fa): Fa úgy áll elõ a Fa0 bináris fából, hogy az % utóbbi minden egyes levelében levõ értéket 1-gyel megnöveljük. | ?- fa_noveltje(node(leaf(1),node(leaf(2),leaf(3))), Fa). Fa = node(leaf(2),node(leaf(3),leaf(4))) ? ; no 4. Lista hosszának meghatározása Egy lista hosszának az elemei számát nevezzük. % lista_hossza(*Lista, -Hossz): A Lista egészlista hossza Hossz. | ?- lista_hossza([1,3,5], H). H = 3 ? ; no 5*. (szorgalmi, otthoni feladat) Lista hosszának meghatározása -- jobbrekurzív változat % lista_hossza2(*Lista, -Hossz): A Lista egészlista hossza Hossz. % Jobbrekurzív változat Segédeljárás szükséges. 6. Egészlista minden elemének növelése % lista_noveltje(*L0, ?L): Az L egészlista úgy áll elõ az L0 % egészlistából, hogy az utóbbi minden egyes elemét 1-gyel megnöveljük. | ?- lista_noveltje([1,5,2], L). L = [2,6,3] ? ; no 7. Egy lista utolsó elemének meghatározása % lista_utolso_eleme(*L, ?Ertek): Az L egészlista utolsó eleme Ertek. | ?- lista_utolso_eleme([5,1,2,8,7], E). E = 7 ? ; no 8. Egy fa leveleiben található értékek felsorolása % fa_levelerteke(*Fa, -Ertek): A Fa bináris fa egy levelében található % érték az Ertek. Az eljárás nemdeterminisztikus módon sorolja fel az összes levélértéket. A felsorolás sorrendjére nem teszünk megkötést. | ?- fa_levelerteke(node(leaf(1),node(leaf(2),leaf(3))), E). E = 1 ? ; E = 2 ? ; E = 3 ? ; no 9. Egy fa részfáinak a felsorolása Egy fa (nem feltétlenül valódi) részfájának nevezzük saját magát, valamint - ha a fa egy csomópont - akkor a bal és jobboldali ág részfáit. % fa_reszfaja(*Fa, -Resz): Resz a Fa bináris fa részfája. A fenti eljárás nemdeterminisztikus, azaz többféleképpen sikerül: a Resz változóban fel kell sorolnia a Fa összes részfáját. A felsorolás sorrendjére nem teszünk megkötést. | ?- fa_reszfaja(node(leaf(1),node(leaf(2),leaf(3))), Fa). Fa = node(leaf(1),node(leaf(2),leaf(3))) ? ; Fa = leaf(1) ? ; Fa = node(leaf(2),leaf(3)) ? ; Fa = leaf(2) ? ; Fa = leaf(3) ? ; no Gondolja meg, hogy a predikátum klózai sorrendjének változtatásakor hogyan változik a felsorolás sorrendje! A fa_reszfaja eljárás felhasználásával írja meg a 9. feladat megoldását, fa_levelerteke2 néven! 10. Egy lista prefixumainak a felsorolása Egy L n-elemû lista prefixumának nevezzünk egy listát, ha az az L elsõ k elemét tartalmazza (az L-beli sorrend megtartásával), ahol 0 =< k =< n. % lista_prefixuma(*L0, -L): L az L0 egészlista prefixuma. A fenti eljárás nemdeterminisztikus, azaz többféleképpen sikerül: az L változóban fel kell sorolnia a L0 összes prefixumát. A felsorolás sorrendjére nem teszünk megkötést. | ?- lista_prefixuma([1,4,2], Sz). Sz = [1,4,2] ? ; Sz = [1,4] ? ; Sz = [1] ? ; Sz = [] ? ; no Gondolja meg, hogy a predikátum klózai sorrendjének változtatásakor hogyan változik a felsorolás sorrendje! 11. Fa mélységének meghatározása Egy fa mélységén az egymásba skatulyázott node struktúrák maximális számát értjük. % fa_melysege(*Fa, ?M): A Fa bináris fa mélysége M. | ?- fa_melysege(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3))), N). N = 2 ? ; no | ?- fa_melysege(node(leaf(1),node(leaf(2),node(leaf(4),leaf(3)))), N). N = 3 ? ; no Tipp: az aritmetikai kifejezésekben megengedett a max függvény használata, pl | ?- X is max(2,3)+1. ---> X = 4 ? ; no 12. Egy fa legbaloldalibb levélértékének meghatározása % fa_balerteke(*Fa, ?Ertek): A Fa bináris fa legbaloldalibb levelében % az Ertek egész érték szerepel. | ?- fa_balerteke(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3))), E). E = 1 ? ; no 13. Egy fa legjobboldalibb levélértékének meghatározása % fa_jobberteke(*Fa, ?Ertek): A Fa bináris fa legjobboldalibb levelében % az Ertek egész érték szerepel. | ?- fa_jobberteke(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3))), E). E = 3 ? ; no 14. Egy fa rendezettségének eldöntése Egy fát rendezettnek mondunk, ha a levelek értékei, balról jobbra haladva szigorúan monoton növõ sorozatot alkotnak. % fa_rendezett(*Fa): A Fa bináris fa rendezett. | ?- fa_rendezett(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3)))). no | ?- fa_rendezett(node(node(leaf(1),leaf(3)), node(leaf(5),node(leaf(6),leaf(9))))). yes A megoldásban célszerû az elõzõ két feladat eljárásait segédeljárásként felhasználni, így nem szükséges további segédeljárást definiálni. Keressen hatékonyabb megoldást is, amelyben a fastruktúrát csak egyszer járja be! Ebben feltételezheti, hogy a fa csak pozitív számokat tartalmaz (fa_rendezett2). Ehhez a megoldáshoz szükség lehet egy megfelelõ segédeljárásra. 15. Fa tükörképének képzése % fa_tukorkepe(*Fa0, ?Fa): Fa a Fa0 bináris fa tükörképe. | ?- fa_tukorkepe(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3))), Fa). Fa = node(node(leaf(3),leaf(2)),node(leaf(4),leaf(1))) ? ; no | ?- fa_tukorkepe(node(node(leaf(1),leaf(4)),node(leaf(4),leaf(1))), Fa). Fa = node(node(leaf(1),leaf(4)),node(leaf(4),leaf(1))) ? ; no 16. Fa tükörszimmetrikus voltának ellenõrzése % fa_tukros(*Fa): A Fa bináris fa tükörszimmetrikus. | ?- fa_tukros(node(node(leaf(1),leaf(4)),node(leaf(4),leaf(1)))). yes | ?- fa_tukros(node(node(leaf(1),leaf(4)),node(leaf(2),leaf(3)))). no 17. 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 18. Lista adott helyen kezdõdõ szuffixuma Egy L lista szuffixumának nevezünk egy listát, ha az az L utolsó valahány elemét tartalmazza, az L-beli sorrend megtartásával. % suffix_before(+Whole, ?Suffix, +Before): A Whole zárt végû 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 19. Részlista képzése % sublist(+Whole, ?Part, +Before, +Length): A Whole zárt végû % 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