% % % Deklaratív programozás % % 2. Prolog gyakorlat % % 2024 október 22. % % % Prolog programozás: egyszerű listakezelés, bináris fák, aritmetika % % MEGOLDÁSOK % % ----------------------------------------------------------------------- % 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 % fa_pontszama(+Fa, -N): A Fa bináris fa csomópontjainak száma N. fa_pontszama(leaf(_), 0). fa_pontszama(node(L,R), P) :- fa_pontszama(L, LP), fa_pontszama(R, RP), P is LP+RP+1. % 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 % 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(leaf(X), leaf(Y)) :- Y is X+1. fa_noveltje(node(L,R), node(NL,NR)) :- fa_noveltje(L, NL), fa_noveltje(R, NR). % 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 % fa_levelerteke(*Fa, -Ertek): A Fa bináris fa egy levelében található % érték az Ertek. fa_levelerteke(leaf(E), E). fa_levelerteke(node(L,_), E) :- fa_levelerteke(L, E). fa_levelerteke(node(_,R), E) :- fa_levelerteke(R, E). % 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 - 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! % fa_reszfaja(+Fa, -Resz): Resz a Fa bináris fa részfája. fa_reszfaja(Fa, Fa). fa_reszfaja(node(L,_), Fa) :- fa_reszfaja(L, Fa). fa_reszfaja(node(_,R), Fa) :- fa_reszfaja(R, Fa). % A fa_reszfaja eljárás felhasználásával írja meg a 3. feladat % megoldását, fa_levelerteke2 néven! % fa_levelerteke2(+Fa, -Ertek): A Fa bináris fa egy levelében található % érték az Ertek. fa_levelerteke2(Fa, E) :- fa_reszfaja(Fa, leaf(E)). % 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([], _). reszsorozata([Y|S], [X|L]) :- ( Y = X -> reszsorozata(S, L) ; reszsorozata([Y|S], L) ). % 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) member_a(X, L) :- app(_, [X|_], L). % 1. lépés: app/3 1. argumentuma érdektelen (lásd a kódot fent): % is_a_suffix_of(Suff, List): Suff is a suffix of List is_a_suffix_of(B, B). is_a_suffix_of(B, [_|C]) :- is_a_suffix_of(B, C). % member_1(X, L) :- is_a_suffix_of([X|_], L). % 2. lépés [X|_] helyett X-et adjuk át 1. paraméterként: member_(X, [X|_]). member_(X, [_|C]) :- member_(X, C). % 7. Adott lista eleme és az elem elhagyásával keletkező lista % Írja meg a select/3 könyvtári (library(lists)) eljárás select(-,+,-) % módját megvalósító predikátumot % a. select_a néven az app/3-ra vezetve vissza select_a(X, L, R) :- app(Pref, [X|T], L), app(Pref, T, L). % b. select_ néven rekurzív predikátumként (szorgalmi) select_(X, [X|R], R). select_(X, [Y|L], [Y|R]) :- select_(X, L, R). % 8. Lista n.-edik eleme % Írja meg a nth0/3 könyvtári (library(lists)) eljárás nth0(-,+,-) % módját megvalósító predikátumot % a. nth0_a néven az app/3-ra vezetve vissza nth0_a(N, L, E) :- length(Pref, N), app(Pref, [E|_], L). % b. nth0_ néven rekurzív predikátumként (szorgalmi) nth0_(0, [X|_], X). nth0_(N, [_|L], X) :- N > 0, N1 is N-1, nth0_(N1, L, X). % Aritmetikai kifejezések % ----------------------- % A Channel 4 angol 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(Szam) :- integer(Szam), Szam > 0. alapkif(Kif) :- alapkif_reszek(Kif, K1, K2), alapkif(K1), alapkif(K2). % alapkif_reszek(Kif, K1, K2): Kif a négy alapművelet valamelyikével % képzett kifejezés, melynek operandusai K1 és K2. alapkif_reszek(A+B, A, B). alapkif_reszek(A-B, A, B). alapkif_reszek(A*B, A, B). alapkif_reszek(A/B, A, B). % alapkif_reszek1(Kif, K1, K2): ugyanaz mint alapkif_reszek(Kif, K1, K2) alapkif_reszek1(Kif, A, B) :- Kif =.. [Op,A,B], memberchk(Op, [+,-,*,/]). % 9. 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(Szam) :- integer(Szam), Szam > 0. cd_kif(Kif) :- alapkif_reszek2(Kif, K1, K2), alapkif(K1), alapkif(K2). % alapkif_reszek(Kif, K1, K2): Kif a négy alapművelet valamelyikével % képzett kifejezés, melynek operandusai K1 és K2, és amelyben minden % részkifejezés számértéke egy pozitív egész. alapkif_reszek2(A+B, A, B). alapkif_reszek2(A-B, A, B) :- A > B. alapkif_reszek2(A*B, A, B). alapkif_reszek2(A/B, A, B) :- B =\= 0, integer(A) mod integer(B) =:= 0. % 10. 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(K, L) :- integer(K), !, L = [K]. kif_szamok(K, L) :- alapkif_reszek(K, A, B), kif_szamok(A, LA), kif_szamok(B, LB), append(LA, LB, L). % Otthoni, szorgalmi feladat: % 11. Í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. :- use_module(library(lists), [subseq0/2, permutation/2]). cd_megold(Is0, Target, Expr) :- subseq0(Is0, Is1), permutation(Is1, Is2), levelek_kif(Is2, Expr), Target =:= Expr. levelek_kif([Int], Int) :- integer(Int). levelek_kif(Is, Expr) :- append(IsLeft, IsRight, Is), IsLeft \== [], IsRight \== [], levelek_kif(IsLeft, LExpr), levelek_kif(IsRight, RExpr), alapkif_reszek2(Expr, LExpr, RExpr).