BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak |
Nappali tagozat
2001/2002-es tanév
|
n*m
parcella van a kertben (hosszában n
, széltében
m
). Ismerjük a fák pontos helyét, továbbá a sátrak számát soronként és
oszloponként. A fát, amelyhez a sátor hozzá van kötve, a sátor saját fájának nevezzük.
Meghatározandó a sátrak helyzete a saját fájukhoz képest. Példa:
1 --------> m 1 0 2 0 2 1 +--+--+--+--+--+ 1 | |F | | | | | +--+--+--+--+--+ | 1 | | | | | | | +--+--+--+--+--+ | 0 | | |F | |F | | +--+--+--+--+--+ v 3 | | | | | | +--+--+--+--+--+ n 0 |F | | | |F | +--+--+--+--+--+ |
1 0 2 0 2 +--+--+--+--+--+ 1 | | F-S | | | +--+--+--+--+--+ 1 | | | | |S | +--+--+--+--+|-+ 0 | | |F | |F | +--+--+|-+--+--+ 3 |S | |S | |S | +|-+--+--+--+|-+ 0 |F | | | |F | +--+--+--+--+--+ |
|
1. ábra. Egy feladvány (n=5 , m=5 ) |
2. ábra. A feladvány egy megoldása |
Előfordulhat, hogy egyes sorokban, ill. oszlopokban nem írjuk elő a sátrak számát: ezt a megfelelő sor, ill. oszlop elején álló negatív szám jelzi. Példa:
1 --------> m 1 0 -1 0 2 1 +--+--+--+--+--+ 1 | |F | | | | | +--+--+--+--+--+ | 1 | | | | | | | +--+--+--+--+--+ |-1 | | |F | |F | | +--+--+--+--+--+ v 3 | | | | | | +--+--+--+--+--+ n 0 |F | | | |F | +--+--+--+--+--+ |
3. ábra. Negatív szám jelzi, ha nem írjuk elő a sátrak számát egy-egy sorban vagy oszlopban
satrak
néven olyan Prolog-eljárást, amely egy
feladvány összes megoldását előállítja!
A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.
A Prolog-eljárás bemenő paramétere egy
satrak(Ss, Os, Fs)
Ss
a sátrak soronkénti számát tartalmazó lista,
Os
a sátrak oszloponkénti számát tartalmazó lista és
Fs
a fák sorát és oszlopát azonosító (i,j)
párok lexikografikusan rendezett listája.
Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:
satrak([1,1,0,3,0], [1,0,2,0,2], [1-2,3-3,3-5,5-1,5-5])
(i,j)
párt i-j
alakú Prolog-struktúrával írjuk le.
A Prolog-eljárás kimenő paramétere egy olyan lista, amely - a fák Fs
-beli
megadási sorrendjét követve - a sátrak saját fájukhoz viszonyított helyzetét írja le. Egy
sátor helyzetét a megfelelő égtájat jelölő betűvel adjuk meg:
w (west) - a sátor a saját fájától nyugatra áll,
| n (north) - a sátor a saját fájától északra áll,
|
e (east) - a sátor a saját fájától keletre áll,
| s (south) - a sátor a saját fájától délre áll.
|
A 2. ábrán látható megoldást írja le például az alábbi lista:
[e,s,n,n,n]
satrak/2
Prolog-eljárás paramétereinek típusát a következő - megjegyzésként
megadott - Prolog-típusdefiníciók írják le.
% :- type fLeiro ---> satrak(sSzS, sSzO, list(parc)). % :- type sSzS == list(int). % :- type sSzO == list(int). % :- type parc == int-int. % :- type irany ---> n % észak % ; e % kelet % ; s % dél % ; w. % nyugat % :- type sHelyek == list(irany). % :- pred satrak(fLeiro::in, sHelyek::out).
A keretprogram bemenete egy olyan szöveges állomány, amelynek soraiban a feladványmátrix sorai vannak; az üres parcellákat "-" jel jelöli.
1 0 2 0 2 1 - F - - - 1 - - - - - 0 - - F - F 3 - - - - - 0 F - - - F |
4. ábra. A bemenő állomány tartalma az 1. ábrán látható feladvány esetén |
A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.
A Prolog-keretprogram három eljárást exportál:
satrak_be(file::in, fLeiro::out)
satrak_ki(file::in, sHelyek::in, fLeiro::in)
megold(file::in, file::in)
satrak/2
eljárásra.
A keretprogram felhasználja a file
típust:
% :- type file == atom.A
file
típusú paraméterben a user
atomot megadva a terminálról
vihetünk be, ill. a terminálra irathatunk ki adatokat. Egyébként a megadott nevű
állományba írunk, ill. állományból olvasunk.
A programhoz készítsen dokumentációt - vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:
A dokumentációt elektronikus formában adja be, HTML, esetleg ASCII formátumban, ill. azt a beadott program szövegében is elhelyezheti kommentárként.
satrak.pl
nevű állományban kell elhelyezni. Megengedett
Prolog modulok használata, ekkor a satrak.pl
állomány szövegében el kell
helyezni a többi állomány betöltését végző direktívákat. Az összes
állományt egy VezeteknevKeresztnev
nevű könyvtárban kell elhelyezni.
(Pl. Nagy Péter Sándor a saját megoldását a NagyPeterSandor
könyvtárba
helyezze el. A könyvtárnév ékezeteket ne tartalmazzon!)
A megoldást tartalmazó könyvtárat kérem zip
vagy tar.gz
formában a
szeredi-nlp-hf@iqsoft.hu
címre beküldeni. A beadás folyamatos, végső határideje 2002. január 27., vasárnap 24:00.