Deklaratív programozás

1. Prolog kis házi feladat

2005. február 22.

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

A feladat

Nagyfejűnek nevezünk egy számsorozatot, amelynek első eleme nagyobb-egyenlő mint az utolsó, a második nagyobb-egyenlő mint az utolsó előtti stb. Pontosítva:

Egy a₁ a₂, ..., a_n számsorozat nagyfejű, ha minden 1 <= i <= floor(n/2) esetén a_i >= a_n+1-i, ahol floor(x) az x szám egészrészét jelenti. Példák nagyfejű sorozatokra: 1 1; 4 3 5 2 4.

Megírandó egy program cékla nyelven, amely tartalmazza az alábbi fő függvényt: int nagyfeju(int a){...}, melyben nagyfeju(a) == b jelentése: b (>=2) a legkisebb olyan természetes szám, amely esetén az a természetes szám b alapú számrendszerben felírva nagyfejű:

/* int nagyfeju(int a) = b, ha b (b>=2) a legkisebb olyan természetes szám,
   hogy b alapú számrendszerben felírva a-t egy nagyfejű számot kapunk */
int nagyfeju(int a) {
  ...
}

Példák

| * nagyfeju(4);
2
% mert 4₂ = 1 0 0 nagyfejű

| * nagyfeju(10);
3
% mert 10₃ = 1 0 1 nagyfejű, de 10₂ = 1 0 1 0 nem az

| * nagyfeju(143);
11
% mert 143₁₁ = 1 2 0 nagyfejű, de ...

| * nagyfeju(293);
18
% mert 293₁₈ = 16 5 nagyfejű, de ...

A programot CÉKLA nyelven kell elkészíteni, amely a C deklaratív résznyelve. Ügyeljünk arra, hogy a CÉKLA nem támogatja a C++-ban megszokott // jelölést a megjegyzések esetén. A jobbrekurzív függvények kevesebb memóriát igényelnek, mint az egyéb rekurzív függvények, ezért a feladat megoldása során jobbrekurzív függvények írása ajánlott, ám ez nem kötelező, a pontozásba nem számít bele.

Otthoni tesztkörnyezet

Az innen letölthető nagyfeju.zip archív tartalma segíthet a fejlesztés során. A fájl tartalmaz egy minta nagyfeju.c-t, amit a feladat megoldása során át kell írnunk úgy, hogy mindig helyes választ adjon. Az átírás után a program kipróbálható a nagyfejt.c lefordításával és futtatásával (UNIX alatt a cc nagyfejt.c && ./a.out paranccsal).

A fenti fordítás azonban nem ellenőrzi, hogy a C nyelvnek csak a CÉKLÁ-ban megengedett részhalmazát használjuk-e. Az ellenőrzéshez szükség van egy telepített SICStus Prolog-ra. A CÉKLA-értelmező bináris változatát a letöltött nagyfeju.zip tartalmazza, ceklat.sav néven. Ha a kitömörített fájlok az aktuális könyvtárban vannak, akkor egy próbafuttatás végezhető a sicstus -r ceklat.sav <nagyfeju.ct paranccsal. Az e parancs kimenetében található számok jelentése, hármasával csoportosítva a következő: (a; számolt nagyfeju(a); várt nagyfeju(a)). Újabb tesztesetek a nagyfeju.ct illetve a nagyfejut.c módosításával vehetők fel.

A CÉKLA a SICStus prolog telepítése nélkül is futtatható (bár ez nem ajánlott, mert a félév folyamán amúgy is szükség lesz SICStus-ra, ezért érdemes minél hamarabb telepíteni). A CÉKLA önálló programként Win32 és Linux (glibc2.2 & 2.3) alatt is fut (a linkeket követve letölthető). Jelenleg Windows alatt a CÉKLA rendszert olyan könyvtárba lehet csak telepíteni, amelynek elérési útvonalában nincs szóköz!

Tudnivalók a beadásról

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.c néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2005. március 1., kedd 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).