Deklaratív programozás

0. kis házi feladat

1.0 változat
Utolsó módosítás: 2013-02-27
Kiadás: 2013-02-19
Beadási határidő: 2013-03-03, vasárnap, 23:59

A feladat

Egy S>0 szám A>1 alapú megkevertjét a következőképpen definiáljuk:

Írjuk fel az S számot A alapú számrendszerben. A kapott számjegyeket jelölje S₁, ..., S_n. Az átíráskor nem használhatunk vezető nullákat, azaz S₁ ≠ 0.
A számjegysorozatot vágjuk középen ketté, és tekintsük az S₁, ..., S_k, és az S_k+1, ..., S_n számjegysorozatokat, ahol k:=⌊n/2⌋.
Fésüljük össze a két számjegysorozatot a másodikkal kezdve, a keletkező számjegysorozat
- S_k+1, S₁, S_k+2, S₂, ..., S_n, S_k legyen, ha n páros;
- S_k+1, S₁, S_k+2, S₂, ..., S_n legyen, ha n páratlan.
Az átrendezett számjegysorozatot tekintsük A alapú számrendszerben felírt számnak. Az így kapott szám értékét nevezzük az S szám A alapú megkevertjének.

Írjon olyan programot Cékla nyelven (a C++ nyelv egy deklaratív résznyelvén), amelynek fő függvénye az int megkevert(const int S, const int A){...} függvény.

/* megkevert(S, A) == SK, ha SK az S szám A alapú megkevertje (S>0, A>1).
   Egy S szám A alapú megkevertjét úgy kapjuk meg, hogy az S számot felírjuk
   az A alapú számrendszerben, a számjegyeit egy listával ábrázoljuk, a
   listát a fentiek szerint megkeverjük, majd a kapott lista elemeit
   egy A alapú szám jegyeinek tekintve előállítjuk a keresett értéket.
*/
int megkevert(const int S, const int A) {
  ...
}

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 S < A²:

int megkevert(const int S, const int A) {
  if (S<A) return S;
  return S%A*A + S/A;
}

Példák

|* megkevert(123, 10);
213
|* megkevert(101, 10);
11
|* megkevert(5, 2);
3
|* megkevert(1023, 10);
2130
|* megkevert(11, 3);
5
|* megkevert(246813579, 10);
123456789
|* megkevert(24681357, 10);
12345678
|*

Tudnivalók a beadásról

Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kis házi feladatot - közülük legalább egyet Prolog és legalább egyet Erlang nyelven - meg kell oldani és sikeresen be kell adni. (Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad.)

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.) A beadási határidő 2013. március 3., vasárnap, 23:59.

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