Deklaratív programozás

1. Prolog kis házi feladat

2005. október 13. Jav. 2005. nov. 1.

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

A feladat

Párbafésültnek nevezünk egy számsorozatot, ha páros hosszú, első eleme nagyobb-egyenlő mint az utolsó, a harmadik nagyobb-egyenlő mint az utolsó előtti előtti stb. Pontosítva:

Egy a₁, a₂, ..., a_2n számsorozat párbafésült, ha minden 0 <= i < n esetén a_2i+1 >= a_2n-2i.

Megírandó egy program cékla nyelven, amely tartalmazza az alábbi fő függvényt: int parbafesult(int a){...}, melyben parbafesult(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 párbafésült:

/* int parbafesult(int a) = b, ha b (b>=2) a legkisebb olyan természetes szám,
   hogy b alapú számrendszerben felírva a-t egy párbafésült számot kapunk */
int parbafesult(int a) {
  ...
}

Példák

| * parbafesult(10);
2
% mert 10₂ = 1 0 1 0 párbafésült,

| * parbafesult(4);
3
% mert 4₃ = 1 1 párbafésült,
% de 4₂ = 1 0 0 nem, mert páratlan hosszú

| * parbafesult(29);
7
% mert 29₇ = 4 1 párbafésült,
% de 29₆ = 4 5 nem párbafésült,
% és 29₅ = 1 0 4 nem, mert páratlan hosszú,
% és 29₄ = 1 3 1 nem, mert páratlan hosszú,
% és 29₃ = 1 0 0 2 nem párbafésült,
% és 29₂ = 1 1 1 0 1 nem, mert páratlan hosszú

| * parbafesult(143);
12
% mert 143₁₂ = 11 11 párbafésült, de ...

| * parbafesult(293);
18
% mert 293₁₈ = 16 5 párbafésült, de ...

| * parbafesult(30302239);
76

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. !! letöltések

Otthoni tesztkörnyezet

Az innen letölthető parbafesult.zip archív tartalma segíthet a fejlesztés során. A fájl tartalmaz egy minta parbafesult.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 parbafesultc.c lefordításával és futtatásával (UNIX alatt a cc parbafesultc.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 parbafesult.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 <parbafesult.ct paranccsal. Az e parancs kimenetében található számok jelentése, hármasával csoportosítva a következő: (a; számolt parbafesult(a); várt parbafesult(a)). Újabb tesztesetek a parbafesult.ct illetve a parbafesultc.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. október 31., 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.