BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2001/2002-es tanév, őszi félév

Deklaratív programozás

Házi feladat, 1.0 változat

Lépegető

Ez a leírás a Deklaratív programozás c. tárgyból kiadott féléves házi feladatot ismerteti.

A feladvány

Egy négyzetrács egyes - meghatározott - pontjaiba kell számokat írni 1-től n-ig úgy, hogy minden 1<i<n-re az i-1-gyel és az i-vel jelölt rácspont közötti távolság határozottan kisebb legyen, mint az i-vel és az i+1-gyel jelölt rácspont közötti. (A távolságot a pitagoraszi képlettel számoljuk ki.) Alább látható egy mintafeladvány és a megoldása.

 ? - - - - -
 - - - - ? -
 - ? - - - -
 ? - - - - -
 - - - - - -
 - - ? - - ?
            
 5 - - - - -
 - - - - 3 -
 - 2 - - - -
 1 - - - - -
 - - - - - -
 - - 4 - - 6
1. ábra. Egy feladvány             2. ábra. A feladvány (egyetlen) megoldása

A megoldandó feladat

Írjon lepeget néven olyan Prolog-eljárást, ill. SML-függvényt, 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 Sor-Oszlop párokból álló lista, amelynek elemei egy-egy kitöltendő rácspont (kérdőjel) helyét adják meg. A listáról feltételezhető, hogy az elemei lexikografikusan növekvő sorrendben vannak. Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere: 

[1-1, 2-5, 3-2, 4-1, 6-3, 6-6]

A Prolog-eljárás kimenő paramétere egy olyan - az előbbivel megegyező hosszúságú - lista, amely minden egyes koordinátához hozzárendeli a megfelelő rácspontba írandó számot. A 2. ábrán látható megoldást írja le például az alábbi lista: 

[5, 3, 2, 1, 4, 6]
Az SML-függvény paramétere egy (Sor, Oszlop) párokból álló lista, amelynek elemei egy-egy kitöltendő rácspont (kérdőjel) helyét adják meg. A listáról feltételezhető, hogy az elemei lexikografikusan növekvő sorrendben vannak. Az 1. ábrán bemutatott feladvány esetén például az SML-függvény paramétere: 
[(1,1), (2,5), (3,2), (4,1), (6,3), (6,6)]
Az SML-függvény eredménye az előbbivel megegyező hosszúságú listák olyan listája, amelynek elemei egy-egy megoldást írnak le úgy, hogy nincs közöttük két azonos, és együtt az összes megoldást megadják (a sorrendjük tetszőleges). Az egy-egy megoldást leíró listák minden egyes koordinátához hozzárendelik a megfelelő rácspontba írandó számot. Az 1. ábrán látható feladványnak egyetlen megoldása van, ez a 2. ábrán látható, és az alábbi lista írja le: 
[[5, 3, 2, 1, 4, 6]]

A megírandó függvény, ill. eljárás specifikációja

A lepeget/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 koord      ---> int-int.
% :- type racspontok == list(koord).
% :- type kitoltes   == list(int).
% :- pred lepeget(racspontok::in, kitoltes::out).

A lepeget függvény paraméterének és eredményének típusát a következő SML-típusdefiníciók írják le. 

structure TLepeget =
struct
      type koord      = int * int
      type racspontok = koord list
      type kitoltes   = int list
end

signature Lepeget =
sig
  (* lepeget Rs = az 1..n számok összes olyan permutációja listaként
       ábrázolva, amelynek elemeit rendre egy rács Rs-beli rácspontjaiba
       írva a megadott távolságkritériumnak eleget tevő elrendezést kapunk
  *)
  val lepeget : TLepeget.racspontok -> TLepeget.kitoltes list
end

A keretprogram

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a specifikációs modulokkal és egy, a beadáskor használthoz hasonló tesztsorral innen töltheti le. A házi feladatok teszteléséhez és értékeléséhez ezekkel kompatíbilis programokat fogunk használni. Figyelem! A keretprogramhoz adott tesztesetek tájékoztató jellegűek, nehézségük, méretük a beadott programoktól függően változhat!

A keretprogram bemenete egy olyan szöveges állomány, amelynek egyetlen sorában a rács kitöltendő rácspontjainak koordinátái állnak (Sor, Oszlop) alakban, egy-egy szóközzel elválasztva. 

(1,1) (2,5) (3,2) (4,1) (6,3) (6,6)
3. á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:

lepeget_be(file::in, racspontok::out)
A megnevezett szöveges állományból beolvassa a feladványt, és visszaadja a második argumentumban.
lepeget_ki(file::in, racspontok::in, kitoltes::in)
A megnevezett szöveges állományba kiírja az adott megoldást.
megold(file::in, file::in)
Beolvas egy feladványt 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 lepeget/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.

Az SML-keretprogram három függvényt exportál: 

signature KLepeget =
sig
    val lepeget_be : string -> TLepeget.racspontok
    val lepeget_ki : string * TLepeget.racspontok * TLepeget.kitoltes list -> unit
    val megold     : string * string -> string
end
lepeget_be f
Az f szöveges állományból beolvasott adatokból képzett feladvány.
lepeget_ki(m, fl, mss)
Az fl feladvány és az mss megoldáslista alapján az összes megoldást kiírja az m szöveges állományba.
megold(f, m)
Beolvas egy feladványt az f szöveges állományból és kiírja az összes megoldást az m szöveges állományba. Ehhez természetesen szüksége van a Lepeget.lepeget függvényre. Eredménye az f nevet, a megoldások számát és a futási időt másodpercben tartalmazó füzér.
A bemenetet, ill. a kimenetet a terminálra irányíthatjuk Unix alatt a /dev/stdin, ill. a /dev/stdout, MS-DOS alatt mindkét esetben a con állománynév megadásával.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük 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 ill. függvények feladatát és működését! Írjon minden eljáráshoz és függvényhez fejkommentet!

A két programhoz közös dokumentációt készítsen - 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.

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

A programokat és az elektronikus dokumentációt tömörítve, elektronikus levélben kell elküldeni egy (később innen letölthető) bash szkript segítségével.

A programok és az elektronikus dokumentáció beadási határideje 2001. december 10-e, hétfő, 24 óra. A vizsgaosztályzatban a határidőre beadott nagyfeladat eredményét 15%-os súllyal vesszük figyelembe. A hibátlan nagyfeladatot beadók SML- és/vagy Prolog-programjukkal létraversenyben vesznek részt. A leggyorsabban futó SML-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 30 és 2 közötti pluszpont kapható, a féléves összpontszámhoz a kapott összegnek a negyedét adjuk hozzá.

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell.

dp@inf.bme.hu
Utolsó módosítás: 2001. nov. 4.