BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2007/2008-as tanév

Nagyhatékonyságú logikai programozás

Házi feladat, 1.0. változat

Sátrak

Ez a leírás a Nagyhatékonyságú logikai programozás c. tárgyból kiadott féléves házi feladatot ismerteti.

A feladvány

Egy téglalap alakú kert négyzet alakú, egyforma parcellákra van felosztva. Kezdetben a parcellák többsége üres, egyes parcellákon egy-egy fa áll. Az üres parcellákon - egy-egy szomszédos fához kötve - sátrakat állíthatunk fel, az alábbi feltételekkel:
  1. egy parcellán legfeljebb egy fa vagy egy sátor lehet,
  2. minden fához pontosan egy sátrat kell kötni,
  3. egy sátor akkor köthető egy fához, ha a parcellák, amelyeken állnak, oldalszomszédok,
  4. olyan parcellák, amelyeken sátrak állnak, sem oldal-, sem sarokszomszédok nem lehetnek.
Összesen 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

A megoldandó feladat

Írjon 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)
felépítésű struktúra, ahol

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])
ahol az (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]

A megírandó eljárás specifikációja

A 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

Programját keretprogram segítségével próbálhatja ki. A keretprogramot egy 32 mintapéldából álló tesztsorral együtt innen letöltheti.

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)
A megnevezett szöveges állományból beolvassa a feladványleírót, és visszaadja a második argumentumban.
satrak_ki(file::in, sHelyek::in, fLeiro::in)
A megnevezett szöveges állományba kiírja az adott megoldást a sátorhelyek és a feladványleíró alapján.
megold(file::in, file::in)
Beolvas egy feladványleírót az első paraméterként kapott állományból, és kiírja az ahhoz tartozó összes megoldást a második paraméterben megadott állományba. Ehhez természetesen szüksége van a 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.

Dokumentációs követelmények

A programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövege jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások feladatát és működését! Írjon minden eljáráshoz fejkommentet!

A programhoz készítsen dokumentációt - vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

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.

A beadás módja

A beadás módját később ismertetjük.

szeredi@cs.bme.hu
Utolsó módosítás: 2007. 11. 22.