Deklaratív programozás

2. 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 parja/3 Prolog eljárást, amely az első argumentumában megadott fában kikeresi a második argumentumban megadott kulcshoz tartozó értéke(ke)t és visszaadja azt (felsorolással) a harmadik argumentumban:

% :- pred parja(tree::in,key::inout,value::inout).
% parja(Fa,Kulcs,Ertek):
% Fa-ban Kulcs kulcshoz Ertek érték tartozik

Egy kulcs többször is szerepelhet a megadott fában. Az eljárásnak több módban is működnie kell, alkalmasnak kell lennie arra, hogy kulcsokat soroljon fel, amennyiben az érték adott, valamint arra is, hogy felsorolja a lehetséges kulcs-érték párokat. Figyelem, a fa mindig bemenő argumentum.

Példák

| ?- parja(node(empty,node(empty,empty,1-2),2-2),1,E).
E = 2 ? ;
no

| ?- parja(node(empty,node(node(empty,empty,1-5),empty,1-2),2-2),1,E).
E = 2 ? ;
E = 5 ? ;
no

| ?- parja(node(empty,node(node(empty,empty,1-5),
                           node(empty,empty,2-2),1-2),2-2),3,E).
no

| ?- parja(node(empty,node(empty,empty,3-4),1-2),K,4).
K = 3 ? ;
no

| ?- parja(node(empty,node(empty,empty,3-4),1-2),K,V).
K = 1,
V = 2 ? ;
K = 3,
V = 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-pl2.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).