Deklaratív programozás

0. kis házi feladat

1.0 változat
Utolsó módosítás: 2017-09-13
Kiadás: 2017-09-13
Beadási határidő: 2017-09-24, vasárnap, 23:59

A feladat

Egy S>0 egész szám A>1 alapú átrendezett változatá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_k. Az átíráskor nem használhatunk vezető nullákat, azaz S₁ ≠ 0.
A számjegysorozatot rendezzük át úgy, hogy elöl a páratlan indexű jegyek álljanak, utánuk a páros indexűek: S₁, S₃, ..., S₂, S₄, ... Pontosítva és formalizálva:
- ha k páros, akkor az eredmény S₁, S₃, ..., S_k-1, S₂, S₄, ..., S_k legyen;
- ha k páratlan, akkor az eredmény S₁, S₃, ..., S_k, S₂, S₄, ..., S_k-1 legyen.
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ú átrendezett változatának.

Például az 1234 szám 10-es alapú átrendezett változata 1324, az 1234567 szám 10-es alapú átrendezett változata pedig 1357246.

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

/* atrendezett(S, A) == SK, ha SK az S szám A alapú átrendezett
   változata (S>0, A>1 egész számok).
   Egy S szám A alapú átrendezettjé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 átrendezzük, majd a kapott lista elemeit
   egy A alapú szám jegyeinek tekintve előállítjuk a keresett értéket.
*/
int atrendezett(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 atrendezett(const int S, const int A) {
  if (S<A*A) return S;
  return (S/A/A*A+S%A)*A+S/A%A;
}

Példák

|* atrendezett(123, 10);
132
|* atrendezett(101, 10);
110
|* atrendezett(5, 2);
6                     // mert 5₂ = 1 0 1 és 6₂ = 1 1 0
|* atrendezett(1023, 10);
1203
|* atrendezett(11, 3);
15                    // mert 11₃ = 1 0 2, és 15₃ = 1 2 0
|* atrendezett(162738495, 10);
123456789
|* atrendezett(15263748, 10);
12345678
|*

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.

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.)

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.