Deklaratív programozás, 4. gyakorlat Erlang programozás: struktúrák, visszalépés 2011. 10. 28. ----------------------------------------------------------------------------- A példasorban a fa() és egeszfa() adattípusokat a következő módon definiáljuk: % @type fa() = level | {term(),fa(),fa()}. % @type egeszfa() = level | {integer(),egeszfa(),egeszfa()}. Tehát egy `fa()' típusú Erlang-kifejezés - vagy egy olyan adatot tartalmazó csomópont lehet, amely további két `fa()' típusú értéket tartalmaz; az első a bal részfa, a második a jobb részfa, az adatot pedig címkének nevezzük; - vagy címke nélküli levél, Egy `egeszfa()' olyan `fa()', amelynek minden címkéje egész. A példákban felhasznált változók értéke: T1 = {4, {3,level,level}, {6, {5,level,level}, {7,level,level}}}, T2 = {a, {b, {x,level,level}, level}, {c, level, {d, {x,{e,level,level},level}, {a, {x,level,level},{x,level,level}}}}}. ----------------------------------------------------------------------------- 1. Egészfa minden elemének növelése %% @spec fa_noveltje(F0::egeszfa()) -> F::egeszfa(). %% Az F fa az F0 egészfának olyan másolata, amelynek ugyanannyi levele és %% csomópontja van, mint az F0-nak, ám F minden címkéje pontosan eggyel %% nagyobb, mint az F0 megfelelő címkéje. fa_noveltje(T1) =:= {5,{4,level,level},{7,{6,level,level},{8,level,level}}}. ----------------------------------------------------------------------------- 2. Bináris fa tükörképe %% @spec faTukorkepe(F0::fa()) -> F::fa(). %% F az F0 fa tükörképe. fa_tukorkepe(T1) =:= {4,{6,{7,level,level},{5,level,level}},{3,level,level}}. ----------------------------------------------------------------------------- 3. Bináris fa legszélső címkéjének meghatározása a) %% @spec fa_balerteke(F::fa()) -> {ok, C::term()} | error. %% A nemüres F fa bal oldali szélső címkéje C, amelyre és minden %% felmenőjére igaz, hogy bal oldali gyermek; üres fa esetén `error'. b) %% @spec fa_jobberteke(F::fa()) -> {ok, C::term()} | error. %% A nemüres F fa jobb oldali szélső címkéje C; üres fa esetén `error'. fa_balerteke(T1) =:= {ok, 3}. fa_balerteke(level) =:= error. fa_jobberteke(T1) =:= {ok, 7}. ----------------------------------------------------------------------------- 4. Bináris fa rendezettsége Egy bináris fa rendezett, ha inorder bejárásakor a címkéi szigorúan monoton növekednek, azaz a csomópontjai kielégíti a keresőfa-tulajdonságot: minden egyes csomópont címkéje nagyobb a bal oldali gyermekei címkéinél és kisebb a jobb oldali gyermekei címkéinél. (Tipp a végén.) %% @spec rendezett_fa(F::fa()) -> B::bool(). %% B igaz, ha az F fa rendezett. rendezett_fa(T1) =:= true. rendezett_fa(T2) =:= false. ----------------------------------------------------------------------------- 5. Címke előfordulása (rendezetlen) bináris fában %% @spec tartalmaz(C::term(), F::fa()) -> B::bool(). %% B igaz, ha C az F fa valamely címkéje. tartalmaz(x, T1) =:= false. tartalmaz(x, T2) =:= true. ----------------------------------------------------------------------------- 6. Címke összes előfordulásának száma bináris fában %% @spec elofordul(C::term(), F::fa()) -> N::integer(). %% A C címke az F fában N-szer fordul elő. elofordul(x, T1) =:= 0. elofordul(x, T2) =:= 4. ----------------------------------------------------------------------------- 7. Bináris fa összes címkéjének útvonala Egy adott csomópont útvonalának nevezzük azon csomópontok címkéinek listáját, amelyeken át a fa gyökerétől az adott csomópontig el lehet jutni. %% @type ut() = [term()]. %% @spec utak(F::fa()) -> CimkezettUtak::[{term(), ut()}]. %% A CimkezettUtak lista az F fa minden csomópontjához egy kételemű ennest %% társít, amelynek első eleme a csp. címkéje, második eleme a csp. %% útvonala. (Tipp a végén.) utak(T1) =:= [{4,[]},{3,[4]},{6,[4]},{5,[4,6]},{7,[4,6]}]. utak(T2) =:= [{a,[]}, {b,[a]}, {x,[a,b]}, {c,[a]}, {d,[a,c]}, {x,[a,c,d]}, {e,[a,c,d,x]}, {a,[a,c,d]}, {x,[a,c,d,a]}, {x,[a,c,d,a]}]. ----------------------------------------------------------------------------- 8. Címke összes előfordulása bináris fában útvonallal %% @spec cutak(C::term(), F::fa()) -> Utak::[ut()]. %% Utak azon csomópontok útvonalainak listája F-ben, amelyek címkéje C. a) oldja meg listanézettel és az utak/1 felhasználásával, b) oldja meg memóriatakarékosabban úgy, hogy csak a keresett útvonalakat tárolja az összes útvonal helyett. (Tipp a végén.) cutak(x, T1) =:= []. cutak(x, T2) =:= [{x,[a,b]},{x,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}]. ----------------------------------------------------------------------------- 8 VEZÉR A SAKKTÁBLÁN Feladat: 8 vezér (királynő) elhelyezése a sakktáblán úgy, hogy ne üssék egymást. Az alábbi feladatok egy lehetséges megoldás felépítéséhez vezetnek. %% @type sor() = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8. %% @type oszlop() = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8. % abcdefgh helyett. %% @type jelolt() = [oszlop()]. Mivel egy megoldásban bármely sorban vezér csak . . . X . . . . a többitől különböző oszlopban lehet, ezért a . . . . . . X . megoldások az oszlopindexek permutációival . . X . . . . . leírhatók. Vagyis egy megoldás egy olyan lista, . . . . . . . X amelynek ha az i. eleme j, akkor a sakktábla . X . . . . . . i. sorában a j. oszlopban van vezér. Például . . . . X . . . jobbra a [4,7,3,8,2,5,1,6] megoldás látható. X . . . . . . . Ezzel automatikusan kizárjuk, hogy két vezér . . . . . X . . azonos oszlopban vagy sorban legyen, csak azt (1 2 3 4 5 6 7 8) kell vizsgálni, hogy átlósan ütésben vannak-e. (a b c d e f g h) ----------------------------------------------------------------------------- 9. Listák cipzárazása (vö lists:zip/2, lists:unzip/1) %% @spec zip(Xs::[term()], Ys::[term()]) -> XYs::[{term(), term()}]. %% @spec unzip(XYs::[{term(), term()}]) -> {Xs::[term()], Ys::[term()]}. %% XYs olyan párok listája, amelynek első eleme az Xs, második eleme %% az Ys lista azonos pozíciójú eleme. zip([1,2,3], [a,b,c]) =:= [{1,a},{2,b},{3,c}]. unzip([{1,a},{2,b},{3,c}]) =:= {[1,2,3], [a,b,c]}. ----------------------------------------------------------------------------- 10. Számpárok összeg-különbség párjainak előállítása (koordináta-transzformáció) %% @spec atlok([{R::sor(), C::oszlop()}]) -> %% [Atlok::{integer(), integer()}]. %% Minden {R,C} párhoz egy Atlok számpárt rendel, amelynek első eleme %% R+C, második eleme R-C. %% Ezzel egy {sor(),oszlop()} koordinátához rendelhető, hogy "hányadik" %% átlóban van: az összegnél balról, a különbségnél jobbról számítva. %% Egy 3x3-as táblán az R+C értékek: R-C értékek: Átlók: %% 2 3 4 0 -1 -2 {2,0} {3,-1} {4,-2} %% 3 4 5 1 0 -1 {3,1} {4,0} {5,-1} %% 4 5 6 2 1 0 {4,2} {5,1} {6,0} atlok([{1,1}, {2,3}]) =:= [{2,0}, {5,-1}]. ----------------------------------------------------------------------------- 11. Ütések ellenőrzése Felhasználható az előadáson megismert all_different/1 függvény is: %% @spec all_different(Xs::[any()]) -> B::bool() %% B igaz, ha az L lista minden eleme különbözik. all_different(L) -> length(L) =:= length(lists:usort(L)). %% @spec nem_utik_egymast(Js::jelolt()) -> B::bool(). %% B igaz, ha a vezérek Js-beli elhelyezése helyes, vagyis nem ütik %% egymást egy length(Js) sorból és lists:max(Js) oszlopból álló táblán. nem_utik_egymast([1,3,5]) =:= true. nem_utik_egymast([1,5,3]) =:= false. ----------------------------------------------------------------------------- 12. 1..8 számok összes permutációjának felsorolása %% @spec perms() -> Ps::[jelolt()]. %% Ps az 1..8 számok összes lehetséges permutációját tartalmazó lista. perms() =:= [[1,2,3,4,5,6,7,8], [1,2,3,4,5,6,8,7] | ... ]. ----------------------------------------------------------------------------- 13. 8 vezér -- kimerítő keresés (generate and test) Oldjuk meg a feladatot kimerítő kereséssel: először generáljuk az összes permutációt, majd kiszűrjük azokat, amelyek helyes megfejtések. Felhasználandó: listanézet, perms/0, nem_utik_egymast/1. %% @spec vezerek8_1() -> [jelolt()]. vezerek8_1() =:= [ [1,5,8,6,3,7,2,4] | ... ]. length(vezerek8_1()) =:= 92. ----------------------------------------------------------------------------- 14. 8 vezér -- hatékonyabb megoldás Permutációk generálása közben is végzünk szűrést a részmegoldásra: ha már K=<8 sorhoz rendeltünk oszlopot, a K méretű részmegoldást is ellenőrizhetjük a nem_utik_egymast/1 függvénnyel. Nem használható fel a perms/0 függvény, hiszen a generátorok közé kell a szűréseket betenni. _ = statistics(runtime), % idő lekérdezése V1 = vezerek8_1(), % V1 az összes megoldás {_,Time1} = statistics(runtime), % utolsó lekérdezés óta eltelt idő V2 = vezerek8_2(), % V2 az összes megoldás {_,Time2} = statistics(runtime), % utolsó lekérdezés óta eltelt idő lists:sort(V1) =:= lists:sort(V2) % sorrendet nem kötjük meg andalso Time2 < Time1. % de bizonyosan gyorsabb ----------------------------------------------------------------------------- 15. A sakktábla mérete 8 helyett N (paraméter). Keressük a megoldásokat kimerítő kereséssel az 1..N számok permutációi között. ----------------------------------------------------------------------------- 16. N méretű sakktábla hatékonyabb megoldása: a részmegoldásokat is ellenőrizzük. ----------------------------------------------------------------------------- SEGÍTSÉG A MEGOLDÁSHOZ ----------------------------------------------------------------------------- 4. Bináris fa rendezettsége A megoldásban célszerű a 3.a) és 3.b) feladatok megoldá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. Pl: % rendezett_fa_2_kozott(Also::term(),Felso::term(),F::fa()) -> B::bool(). % B igaz, ha az F rendezett ÉS minden címkéjére AlsoCimkezettUtak::[{C::term(),U::ut()}]. % A CimkezettUtak lista az F fa minden csomópontjához egy kételemű ennest % társít, amelynek első eleme (C) a csp. címkéje, második eleme (U) az % Eddigi útvonal és a csp. útvonala összefűzve. ----------------------------------------------------------------------------- 8. Címke összes előfordulása bináris fában útvonallal b) A megoldás nagyon hasonló a 7. megoldáshoz, de a fa gyökerének címkéjét csak feltételesen tároljuk el. ----- $LastChangedDate: 2012-09-15 17:47:13 +0200 (Sat, 15 Sep 2012) $ ------