BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2005/2006. tanév, őszi félév

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: 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 102 = 1 0 1 0 párbafésült,

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

| * parbafesult(29);
7
% mert 297 = 4 1 párbafésült,
% de 296 = 4 5 nem párbafésült,
% és 295 = 1 0 4 nem, mert páratlan hosszú,
% és 294 = 1 3 1 nem, mert páratlan hosszú,
% és 293 = 1 0 0 2 nem párbafésült,
% és 292 = 1 1 1 0 1 nem, mert páratlan hosszú

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

| * parbafesult(293);
18
% mert 29318 = 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.