Deklaratív Programozás gyakorlat Prolog programozás: struktúrák, listák 2010.02.17. --------------------------------------------------------------------------- Az alábbi példasorban a `fa' adatstruktúrát a következő módon definiáljuk: % :- type fa ---> leaf(int) ; node(fa,fa). Tehát egy Prolog kifejezés `fa' ha az: - levél, azaz egy `leaf' nevű struktúra, amelynek egyetlen argumentuma egy egész szám; vagy - csomópont, azaz egy node nevű kétargumentumú struktúra, amelynek mindkét argumentuma `fa'. Famintának hívunk egy Prolog kifejezést, ha egy a fenti módon definiált fakifejezésbol származtatható úgy, hogy a levelekben az egész számok helyére különböző változókat írunk. Az egészlista olyan lista, melynek elemei egészek: % :- type egészlista ---> [] ; [int|egészlista]. Listamintának hívunk egy olyan (zárt) listakifejezést, amelyben az elemek különböző változók. --------------------------------------------------------------------------- Í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. Ha ilyeneken kívül is szükséges segédeljárás definiálása, azt külön jelezzük. A fejkommentekben használt ún. módjelölések 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. Fa csomópontjainak 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 Gondolja meg, hogy megoldása működőképes-e a fa_pontszama(+Fa, ?N) módban, azaz akkor is, ha a második argumentum nem változó, hanem adott egész: | ?- fa_pontszama(node(leaf(1),node(leaf(2),node(leaf(4),leaf(3)))), 3). yes | ?- fa_pontszama(node(leaf(1),node(leaf(2),node(leaf(4),leaf(3)))), 2). no 2. Fa mélysége 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 3. Lista hossza 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 4. 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 5. Számlista minden elemének növelése % lista_noveltje(+L0, ?L): Az L számlista úgy áll elő az L0 % számlistá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 6. 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 7. 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 8. Egy lista utolsó elemének meghatározása % lista_utolso_eleme(+L, ?Ertek): A Lista egészlista utolsó eleme Ertek. | ?- lista_utolso_eleme([5,1,2,8,7], E). E = 7 ? ; no 9. Egy fa részfái 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 10. Egy lista szuffixumai Egy L n-elemű lista szuffixumának nevezzünk egy listát, ha az az L utolsó k elemét tartalmazza (az L-beli sorrend megtartásával), ahol 0 =< k =< n. % lista_szuffixuma(+L0, -L): L az L0 szuffixuma. A fenti eljárás nemdeterminisztikus, azaz többféleképpen sikerül: az L változóban fel kell sorolnia a L0 összes szuffixumát. A felsorolás sorrendjére nem teszünk megkötést. | ?- lista_szuffixuma([1,4,2], Sz). Sz = [1,4,2] ? ; Sz = [4,2] ? ; Sz = [2] ? ; Sz = [] ? ; no 11. Adott elemszámú listaminta előállítása % listaminta_adott_hosszal(-Listaminta, +Hossz): A Listaminta hossza Hossz. | ?- listaminta_adott_hosszal(L, 4). L = [_A,_B,_C,_D] ? ; no 12. Adott számnál kisebb-egyenlő mélységű faminták előállítása % faminta_melysege_max(-Faminta, +MaxMelyseg): % A Faminta binárisfa-minta mélysége =< MaxMelyseg. Az eljárás nemdeterminisztikus módon sorolja fel az összes az adott mélységnél kisebb-egyenlő mélységű famintákat. A felsorolás sorrendjére nem teszünk megkötést. | ?- faminta_melysege_max(FM, 2). FM = leaf(_A) ? ; FM = node(leaf(_A),leaf(_B)) ? ; FM = node(leaf(_A),node(leaf(_B),leaf(_C))) ? ; FM = node(node(leaf(_A),leaf(_B)),leaf(_C)) ? ; FM = node(node(leaf(_A),leaf(_B)),node(leaf(_C),leaf(_D))) ? ; no 13. 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 14. 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 15. Egy fa leveleiben található értékek % 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 16. Egy fa rendezettsége 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ű a 6. és 7. 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. Ehhez egy megfelelő segédeljárás szükséges. 17. Adott számú csomópontból álló faminták előállítása % faminta_adott_pontszammal(-Faminta, +Pontszam): A Faminta % binárisfa-minta csomópontjainak száma Pontszam. Az eljárás nemdeterminisztikus módon sorolja fel az összes az adott számú csomópontot tartalmazó famintákat. A felsorolás sorrendjére nem teszünk megkötést. Segédeljárásra szükség lehet. | ?- faminta_adott_pontszammal(FM, 3). FM = node(leaf(_A),node(leaf(_B),node(leaf(_C),leaf(_D)))) ? ; FM = node(leaf(_A),node(node(leaf(_B),leaf(_C)),leaf(_D))) ? ; FM = node(node(leaf(_A),leaf(_B)),node(leaf(_C),leaf(_D))) ? ; FM = node(node(leaf(_A),node(leaf(_B),leaf(_C))),leaf(_D)) ? ; FM = node(node(node(leaf(_A),leaf(_B)),leaf(_C)),leaf(_D)) ? ; no