Deklaratív programozás 2. Prolog gyakorlat 2024 október 22. 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. Fastruktúrákkal kapcsolatos feladatok ------------------------------------- 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)). 1. 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. 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 3. 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 4. 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 - 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 3. feladat megoldását, fa_levelerteke2 néven! Listákkal kapcsolatos feladatok ------------------------------- 5. Egy lista részsorozata reszsorozata(*ReszSor, *Lista): a ReszSor számlista az Lista számlistából 0 vagy több elem elhagyásával áll elő. | ?- reszsorozata([2,4,4], [1,2,4,4]). true ? ; no | ?- reszsorozata([2,2,4], [1,2,4,4]). no Az előadáson ismertettük az app/3 eljárást, amely a beépített append/3-mal azonos: % app(A, B, C): A és B listák összefűzése a C lista, C = A ++ B app([], B, B). app([X|A], B, [X|C]) :- app(A, B, C). Az alábbi feladatokban egyes listakezelő eljárásokat kell megvalósítani, kétféle módon: a. nem-rekurzív módon az app/3-ra vezetve vissza; b. egy rekurzív predikátum elkészítésével, amely az a. megoldás és a fenti app/3 kód kombinálásából származtatható -- szorgalmi (otthoni) feladatként 6. Lista eleme Írja meg a member/2 beépített eljárással azonos predikátumot a. member_a néven az app/3-ra vezetve vissza b. member_ néven rekurzív predikátumként (szorgalmi) 7. Lista eleme és az elem elhagyásával keletkező lista Írja meg a select/3 könyvtári (library(lists)) eljárással azonos predikátumot a. select_a néven az app/3-ra vezetve vissza b. select_ néven rekurzív predikátumként (szorgalmi) 8. Lista n.-edik eleme Írja meg a nth0/3 könyvtári (library(lists)) eljárással azonos predikátumot a. nth0_a néven az app/3-ra vezetve vissza b. nth0_ néven rekurzív predikátumként (szorgalmi) Aritmetikai kifejezésekkel kapcsolatos feladatok ------------------------------------------------ A Channel 4 brit TV-csatorna több évtizede sugározza a Countdown nevű vetélkedőt. A vetélkedőben kétfajta feladat van: nyelvi és matematikai. A matematikai feladatok esetében adott 6 kisebb szám, 1 és 100 között -- ezeket nevezzük építőköveknek, valamint egy háromjegyű célszám 100 és 999 között. A játékosok feladata az, hogy egy olyan aritmetikai kifejezést találjanak, amelyre a következők teljesülnek: a, a kifejezés értéke a célszám, b. csak a négy alapművelet fordul benne elő, c, operandusként csak az adott 6 építőkő fordulhat elő, mindegyik legfeljebb annyiszor, ahányszor az építőkővek között előfordul, d. a kifejezés kiértékelése során minden részeredmény pozitív egész kell legyen, így pl. a 3/4, 2*2-4, (8-4)-5 részkifejezések nem megengedettek. A 2024 október 17-i vetélkedő feladatai: - építőkövek: 25 50 9 10 5 6, célszám: 973 - építőkövek: 25 3 3 9 5 2, célszám: 856 - építőkövek: 75 100 9 5 1 6, célszám: 331 - építőkövek: 25 9 1 10 3 6, célszám: 602 9. Alapműveletes kifejezés ellenőrzése alapkif(*Kif): Kif egy Prolog kifejezés, amely pozitív egész számokból a négy alapművelettel áll elő. | ?- alapkif(1+2*3-5/6). yes | ?- alapkif(1+2*3-5^6). no 10. Countdown megszorítás ellenőrzése cd_kif(*Kif): Kif egy Prolog kifejezés, amely pozitív egész számokból a négy alapművelettel áll elő, és amelyben minden részkifejezés számértéke egy pozitív egész. | ?- cd_kif(1+2*3-5/6). no | ?- cd_kif(1+2*(3-5)). no | ?- cd_kif(2*(3-3)). no | ?- cd_kif(1+2*3-12/6). yes 11. Egy kifejezésben előforduló építőkövek (számok) kif_szamok(*Kif, ?L): Az L lista a Kif kifejezésben előforduló számok listája, előfordulási sorrendben, ahol Kif csak a négy alapműveletet tartalmazhatja. | ?- kif_szamok(1+2*3-5/6, L). L = [1,2,3,5,6] ? ; no Otthoni, szorgalmi feladat: 12. Írjon egy countdown feladvány megoldót! cd_megold(*Epitokovek, *Celszam, -Kif): Kif egy olyan aritmetikai kifejezés, amelyre teljesülnek az alábbi feltételek: a, Kif értéke a Celszam, b. Kif-ben csak a négy alapművelet fordul elő, c, Kif-ben operandusként csak az Epitokovek lista elemei fordulhatnak elő, mindegyik legfeljebb annyiszor, ahányszor az Epitokovek listában előfordul, d. Kif kiértékelése során minden részeredmény pozitív egész kell legyen. | ?- cd_megold([1,2,4,5,5,10], 930, Kif). % ... sok megoldás, de mindegyik a következő két megoldás % valamelyikével ekvivalens: Kif = ((4*5-1)*5-2)*10 ? Kif = ((5*5-2)*4+1)*10 ?