Deklaratív programozás

Definíciók

Legyenek A, B és N egész számok, ahol A>0, B>0 és N≥2. Az A és B számoknak egy N alapú (számrendszerben képzett) KL különbözõségi listáját a következõképpen definiáljuk:

• Jelöljük k-val a max(A,B) szám N alapú számrendszerben való felírásához szükséges számjegyek számát. Írjuk fel az A és B számokat N alapú számrendszerben! A kapott számjegyeket jelölje rendre A₁, ..., A_k és B₁, ..., B_k, ahol a kisebbik számot vezetõ nullákkal k számjegyûre egészítjük ki, ha k-nál kevesebb számjegybõl áll.
• A KL különbözõségi lista egy k hosszúságú lista, amelynek i-edik eleme 0 ha A_i=B_i, és 1 egyébként.

Például, ha A=10234, B=223 és N=10 (ahol az itt leírt számok 10-es számrendszerben értelmezendõk), akkor k=5, A₁ A₂ A₃ A₄ A₅ = 1 0 2 3 4, B₁ B₂ B₃ B₄ B₅ = 0 0 2 2 3, és így a különbözõségi lista KL = 1 0 0 1 1.

Egy másik példa: A=38, B=44 és N=2 (ahol az itt leírt számok 10-es számrendszerben értelmezendõk). Ez esetben k=6, hiszen a nagyobbik szám, 44 bináris alakja 6-jegyû. A számjegylisták:
A₁ A₂ A₃ A₄ A₅ A₆ = 1 0 0 1 1 0 és B₁ B₂ B₃ B₄ B₅ B₆ = 1 0 1 1 0 0, és így a különbözõségi lista KL = 0 0 1 0 1 0.

Vegyük észre, hogy N=2 esetén a különbözõségi lista úgy is elõállítható, hogy az A és B számokra a bitenkénti "kizáró vagy" (XOR) mûveletet alkalmazzuk, képezzük az így kapott szám bináris jegyeinek listáját, majd ezt a listát elölrõl 0 jegyekkel kiegészítjük szükség esetén úgy, hogy hossza megegyezzék a nagyobb szám bináris jegyeinek számával.

A feladat

Írjon olyan programot Cékla nyelven (a C++ nyelv egy deklaratív résznyelvén), amelynek fõ függvénye az

int klista(const int A, const int B, const int N, const list KL){...}

/* klista(A, B, N, KL) == V, ahol V = 1, ha KL az A és B számok N alapú
   különbözõségi listája, a fenti definíció értelmében, egyébként pedig V = 0.
   (A>0, B >0; N≥2 egész számok, KL egy lista).  */
int klista(const int A, const int B, const int N, const list KL)
   { ...  }

A jobbrekurzív függvények kevesebb memóriát használnak, mint az egyéb rekurzív függvények, ezért a használatukat ajánljuk, azonban a pontozáskor csak azt vizsgáljuk, hogy a program a megadott (néhány másodperces) idõkorláton belül elõállítja-e a helyes megoldást.

Mintamegoldás speciális esetre

Az alábbi mintamegoldás csak akkor mûködik helyesen, ha A, B < N2 és a két szám közül legalább az egyik ≥ N.

int klista(const int A, const int B, const int N, const list KL) {
  if (KL == nil) return 0;
  if (tl(KL) == nil) return 0;
  if (tl(tl(KL)) != nil) return 0;
  return (hd(KL) == (A/N!=B/N)) *
     (hd(tl(KL)) == (A%N!=B%N));
}

Példák

|* klista(12, 23, 10, cons(1,cons(1,nil))).
1
|* klista(12, 23, 10, nil).
0
|* klista(12, 22, 10, cons(1,cons(1,nil))).
0
|* klista(12, 22, 10, cons(1,cons(0,nil))).
1
|* klista(12, 2, 10, cons(1,cons(0,nil))).
1
|* klista(12, 13, 10, cons(0,cons(1,nil))).
1
|* klista(12, 13, 10, cons(1,nil)).
0
|* klista(10234, 223, 10, cons(1,cons(0,cons(0,cons(1,cons(1,nil)))))).
1
|* klista(38, 44, 2, cons(0,cons(0,cons(1,cons(0,cons(1,cons(0,nil))))))).
1
|* klista(38, 44, 2, cons(1,cons(0,cons(1,cons(0,nil))))).
0
|* klista(1, 1, 2, cons(0,nil)).
1
|* klista(1, 1, 2, cons(0,cons(0,nil))).
0
|* klista(1, 1, 2, nil).
0
|*

Tudnivalók a beadásról

A programok készülhetnek MS Windows alatt is, de Linux alatt is mûködniük kell. A beadott programokat Linux környezetben a Cékla rendszerrel teszteljük.

A programot az Elektronikus Tanársegéd segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a nulladik, Cékla nyelvû kis házi feladat, ennek megfelelõen az ETS a beküldött megoldást khf0.cpp néven tárolja el és hivatkozik rá. (A feltöltendõ állomány neve tetszõleges lehet, az ETS átnevezi.)

Az osztályzat megállapításakor a határidõre beadott, minden tesztesetet helyesen megoldó kis házi feladatért plusz 1 pont jár.

A programot mindenkinek saját magának kell elkészítenie, másolás esetén fegyelmi eljárást kezdeményezünk. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.