Deklaratív programozás

2. Prolog kis házi feladat

2003. május 6.

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

A feladat

Tekintsük egy egészeket tartalmazó bináris fa alábbi, Mercury stílusú adattípus-deklarációját, és az ennek megfelelő, a típusba tartozást ellenőrző itree/1 Prolog predikátumot:

% :- type itree ---> lf | br(int, itree, itree).

itree(lf).
itree(br(V,L,R)) :-
	integer(V),
	itree(L),
	itree(R).

Egy ilyen bináris fában egy csomópont vagy levél (együttesen: faelem) helyének jellemzésére egy ún. kiválasztót használhatunk. A kiválasztó egy olyan lista, amelynek minden eleme a left és right atomok egyike. A kiválasztó által megnevezett faelemet úgy kapjuk, hogy a fa gyökeréből elindulva, a left atom esetén a bal részfára, a right atom esetén pedig a jobb részfára lépünk. Például a


br(0, br(1, br(3,lf,lf),
            lf),         
      br(9, br(4,lf,lf),
            br(0,lf,lf)))

fában a 0 értékű csomópont kiválasztója [], a 4 értékűé [right,left].

A feladat az, hogy egy fenti típusú bináris fában keressük meg egy adott egész számnál (határozottan) nagyobb értékeket a kiválasztójukkal együtt, és ezeket a visszalépések során soroljuk fel.

Írjon egy olyan nagyobb/4 Prolog eljárást, amely megkeresi egy adott fában egy adott számnál nagyobb értékű csomópontokat, és ezek értékét és kiválasztóját a visszalépések során felsorolja. (A megoldások sorrendje tetszőleges.)

Az elvárt eredmény az alábbi Mercury stílusú adattípus-deklarációkkal írható le:

% :- type dir      ---> left | right.
% :- type selector ==   list(dir).

A megirandó eljárás fejkommentje:

% nagyobb(+Fa, +Also, -E, -K): a Fa fában a K kiválasztó által
%   meghatározott faelem egy E értékű csomópont, és E > Also.
% :- pred nagyobb(itree::in, integer::in, integer::out, selector::out).

Feltételezheti, hogy az argumentumként átadott fára a fenti itree/1 predikátum sikeresen lefut.

Ha definiál segédeljárásokat, akkor azokat feltétlenül lássa el fejkommenttel!

Példák

| ?- nagyobb(lf, 28, E, K).
no

| ?- nagyobb(br(0, br(1,lf,lf), br(2,lf,lf)), 1, E, K).
E = 2,
K = [right] ? ;
no

| ?- nagyobb(br(0, br(1, br(3,lf,lf),
                         lf),
                   br(9, br(4,lf,lf),
                         br(0,lf,lf))), 2, E, K).
E = 3,
K = [left,left] ? ;
E = 9,
K = [right] ? ;
E = 4,
K = [right,left] ? ;
no

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 nagybetűket.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Linux operációs rendszer alatt is működniük kell. A beadási határidő május 15., csütörtök 24:00.

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