BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2002/2003. tanév, tavaszi félév

Deklaratív programozás

1. Prolog kis házi feladat

2003. március 2.

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 a hozzá tartozó, 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).
A feladat az, hogy egy ilyen típusú fában keressük meg az azon csomópontokhoz tartozó értékeket, amelyekre teljesül, hogy mindkét gyerekük csomópont (tehát nem levél), és a gyerek csomópontokban tárolt értékek nagyobbak a szülő csomópontba írt értéknél.

Írjon egy olyan kisszulo/2 Prolog eljárást, amely tetszőleges sorrendben felsorolja az összes ilyen szülő csomópontbeli értéket! 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!

% kisszulo(+Fa, -Ertek): Ertek a Fa egy olyan csomópontjában található,
%    amelynek mindkét gyereke csomópont, és az ezekbe írt értékek nagyobbak
%    Ertek-nél.
% :- pred kisszulo(itree::in, integer::out).

Példák


| ?- kisszulo(lf, V).
no

| ?- kisszulo(br(0, br(1,lf,lf), br(2,lf,lf)), V).
V = 0 ? ;
no

| ?- kisszulo(br(0, br(1, br(3,lf,lf),
                          lf),
                    br(2, br(4,lf,lf),
                          br(5,lf,lf))), V).
V = 0 ? ;
V = 2 ? ;
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 az első Prolog kis házi feladat, ezért khf-pl1.pl néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket.

Figyelem! A rendszer jelenlegi verziója beadáskor nem ellenőrzi a nevet, ezért csak a tesztelés során derül ki, ha nem megfelelő néven küldték be a megoldást!

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árcius 14., péntek 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).