Deklaratív programozás

2. Prolog kis házi feladat

2002. november 22.

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

A programot tömörítve, elektronikus levélben kell beküldeni. A beküldéshez egy bash szkriptet kell használni. A szkriptet futtatni a bash dpkhfbe.02a paranccsal lehet (feltéve, hogy ezen a néven mentettük el).

Figyelem!

Letöltéskor ügyeljen arra, hogy a sorvég karakterek un*xos LF-ek maradjanak, az Internet Explorer ui. hajlamos átalakítani őket DOS-os CR-LF-fé.
Letöltés egyenesen az ural2 szerverre:wget '../dp-current/dpkhfbe.02a'
Az ural2 szerveren a/usr/local/binkönyvtárban található a bash program.

A szkript elindulaskor elmagyarázza a teendőket (mi legyen az adott könyvtárban, milyen néven stb.). Mielőtt valaki hibára panaszkodna, győződjön meg róla, hogy a hiba az ural2.hszk.bme.hu szerveren is reprodukálható. (A szkript helyes letöltése után.)

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 feladat

Az alábbi Mercury-stílusú típusdefiníció egy fa struktúrát definiál:

%% :- type fa(T) ---> lv ; cs(T, fa(T), fa(T)).

Írjon utlevel/3 funktorú Prolog-eljárást, amely egy ilyen struktúrájú fában egy megadott értékhez felsorolja a gyökértől az érték csomópontbeli előfordulásaihoz vezető utakat! Útnak azt a listát nevezzük, amelynek elemei a bejárás során érintett csomópontbeli értékek, beleértve a gyökeret és a célcsomópontot is.

%% utlevel(Fa, Ert, Ut): Ut a Faban egy Ert értékű csomóponthoz vezető út.
%% :- pred utlevel(fa(T)::in, T::in, list(T)::out).

A Prolog-eljárásnak három paramétere van. Az első (bemenő) paraméterében a bejárandó, tömör (azaz változókat nem tartalmazó) fát kapja meg. A második (szintén bemenő) paraméterében, azt az értéket kapja, amelynek előfordulásait keressük. A harmadik (kimenő) paramétere egy az adott értékű csomóponthoz vezető út.

Az eljárásnak a visszalépések során minden utat pontosan egyszer kell kiadnia. Ha az adott érték egyátalán nem fordul elő a fában, az eljárás hiúsuljon meg. A megoldások sorrendje tetszőleges.

Ha definiál segédeljárásokat, azokat feltétlenül lássa el fejkommenttel! Törekedjék arra, hogy a megoldás hatékony legyen!

Példák


| ?- utlevel(lv, x, Ut).
no

| ?- utlevel(cs(1,lv,lv), 1, Ut).
Ut = [1] ? ;
no

| ?- utlevel(cs(x, cs(y,lv,lv), cs(z,lv,lv)), y, Ut).
Ut = [x,y] ? ;
no

| ?- utlevel(cs(x, cs(y,lv,lv), cs(z,lv,lv)), 1, Ut).
no

| ?- utlevel(cs(3, cs(2,cs(1,lv,lv),lv), cs(4,lv,cs(1,lv,lv))), 1, Ut).
Ut = [3,2,1] ? ;
Ut = [3,4,1] ? ;
no

| ?- utlevel(cs(a, cs(a,lv,lv), cs(a,lv,lv)), a, Ut).
Ut = [a] ? ;
Ut = [a,a] ? ;
Ut = [a,a] ? ;
no

Egyéb követelmények és tudnivalók

Ez az második Prolog kis házi feladat, ezért

 khf-pl2.pl

néven kell beküldeni a megoldást. A beadási határidő december 1., vasárnap 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).