Deklaratív programozás

3. Prolog kis házi feladat

2004. február 24.

A kis házi feladat beadása nem kötelező.

A feladat

Feladatunkban egy bináris fa levelekből és csomópontokból áll össze. A levelek nem tartalmaznak semmilyen értéket, jelölésükre az empty névkonstans szolgál. A csomópontok node/3 struktúrák, melyek első és második argumentuma egy-egy újabb fát jelöl, harmadik argumentuma egy párt ír le. A kulcs-érték pár mindkét tagja egész szám. Fánkat az alábbi jelöléssel írhatjuk le formálisan:

% :- type key == int.
% :- type value == int.
% :- type keyval ---> key-value.
% :- type tree ---> node(tree,tree,keyval)
%	           |empty.

Érvényes fa például a node(empty,node(empty,empty,1-1),1-2) struktúra.

Írjon egy olyan ketfa/3 Prolog eljárást, amely az első argumentumában megadott fát a kulcs-érték párok mentén szétszed két fára és az eredményfákat a második és harmadik argumentumban adja vissza. Az első fa az eredeti fa kulcsait, a második fa az eredeti fa értékeit tartalmazza. Ennek megfelelően ezen fák típusát az alábbi módon adhatnánk meg:

% :- type ktree ---> node(ktree,ktree,key)
%	            |empty.

% :- type vtree ---> node(vtree,vtree,value)
%	            |empty.

Az eljárásnak több módban is működnie kell, alkalmasnak kell lennie fa szétszedésre, valamint fa összerakásra is (amennyiben adott két stree típusú fa). Ha mindhárom fa adott, az eljárásnak el kell tudnia dönteni, hogy igaz-e, hogy az első fa szétszedése a megadott másik két fa. Az elvárt eljárás fejkommentje:

% :-pred ketfa(tree, ktree, vtree).
% :-mode ketfa(in, out, out).
% :-mode ketfa(out, in, in).
% :-mode ketfa(in, in, in).
% ketfa(Fa,Fa1,Fa2): Fa előáll Fa1 és Fa2 összeragasztásával, 
% a kulcsok a Fa1-beli csomópont értékeknek, az értékek a 
% Fa2-beli csomópontértékeknek felelnek meg.

Példák

| ?- ketfa(node(node(empty,empty,8-9),empty,3-4),Fa1,Fa2).
Fa1 = node(node(empty,empty,8),empty,3),
Fa2 = node(node(empty,empty,9),empty,4) ? ;
no

| ?- ketfa(Fa,node(node(empty,empty,8),empty,3), 
              node(node(empty,empty,9),empty,4)).
Fa = node(node(empty,empty,8-9),empty,3-4) ? ;
no

| ?- ketfa(node(node(empty,empty,8-9),empty,3-4),
           node(node(empty,empty,8),  empty,3),
           node(node(empty,empty,  9),empty,  4)).
yes

| ?- ketfa(node(node(empty,empty,8-9),empty,3-4),
           node(node(empty,empty,5  ),empty,3  ),
           node(node(empty,empty,  9),empty,  4)).
no

A programot Prolog nyelven kell elkészíteni.

Beadás, tudnivalók

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a második Prolog kis házi feladat, ezért khf-pl3.pl néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetuket.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Linux operációs rendszer alatt is muködniük kell. A beadási határido március 9., kedd 24:00.

A vizsgaosztályzat megállapításakor a határidore beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár (a 100 pontból).