5. hét: Öröklés, random számok

Ezen a héten az öröklést gyakoroljuk.

Felkészülés

• Jegyzet 7. fejezete, csak az 1-5. és 7. pontok szükségesek.
• InfoC - álvéletlen számok átismétlése

A példafeladat: oldjuk meg, hogy különböző típusú véletlenszám-generátorokat tudjunk egységesen kezelni!

Az álvéletlenszámokat a számítógép egy matematikai műveletsor segítségével állítja elő, aminek a kimenete nem tűnik szabályosnak. A generátornak van belső állapota (seed), ami minden új szám generálásánál megváltozik, így lesz többször futtatva különböző a kimenet.

Azonos seedről indulva, többszöri futtatásra viszont mindig ugyanaz a számsorozat lesz a kimenet. Ezért generátorok seedjét be kell tudni állítani, amit tipikusan a program elején, valamilyen, futásonként változó adattal szoktunk megadni.

A randomgenerátor interfésze kiinduláskor a következő:

class RandomGenerator {
public:
    virtual unsigned next() = 0;
    virtual void setSeed(unsigned newSeed) = 0;
    virtual ~RandomGenerator() {}
};

Töltsd le a kiinduló Code::Blocks projektet innen, és nyisd meg a projektfájlt. Ezeket a fájlokat találod benne:

• random.hpp: a RandomGenerator interfészt és két osztály elődeklarációját tartalmazza. Az elődeklarációkhoz ne nyúlj, sajnos kellenek az automatikus tesztek miatt.
• random.cpp: egyelőre üres, itt kell majd megvalósítanod néhány függvényt
• random_test.cpp: általunk előkészített tesztek, ami automatikusan ellenőrzi az elkészült feladatokat

A projektet lefordítva és lefuttatva azt kell látnod, hogy minden teszteset FAILED. Ahogy haladsz a feladatok megoldásával, ezek egyesével, a legfelsővel kezdve zöldre fognak váltani, feltéve, hogy jól oldottad meg a feladatot.

A legegyszerűbb, Prog1-en is megismert randomgenerátor a C-ből ismerős rand() függvény, aminek a seed-jét az srand függvénnyel állíthatjuk be.

Írj egy CRand osztályt, ami a RandomGenerator leszármazottja, és a rand() - srand() függvényeket használja a tisztán virtuális függvények implementálásához!

Sajnos ez az osztály nem fog minden elvárásnak megfelelően működni, mert a rand() állapotát nem tudjuk példányonként külön tárolni. Így ha a programunkban máshol is használjuk a rand()-ot, vagy két példányunk van a CRand-ból, furcsa dolgok történhetnek. Erre nincs platformfüggetlen megoldás, Linuxon a rand_r(), Windows-on pedig a rand_s() segítségével lehetne javítani.

class CRand : public RandomGenerator {
public:
    virtual unsigned next() {
        return rand();
    }
    virtual void setSeed(unsigned newSeed) {
        srand(newSeed);
    }
};

Néha érdemes magunknak implementálni egy ilyen generátort. Például ha szeretnénk egy játék viselkedését utánozni, akkor a játékéval megegyező randomgenerátort kell használnunk. A Windows XP például az alábbi módon generálja a számokat:

seed = seed * 0x343fd + 0x269EC3;
return (seed >> 0x10) & 0x7FFF;

Írj egy MSRand osztályt, ami RandomGenerator, és a fenti implementációt használja! A seed kezdeti értéke legyen 0!

class MSRand : public RandomGenerator {
    int seed;
public:
    MSRand() : seed(0) {}

    virtual unsigned next() {
        seed = seed * 0x343fd + 0x269EC3;
        return (seed >> 0x10) & 0x7FFF;
    }
    virtual void setSeed(unsigned newSeed) {
        seed = newSeed;
    }
};

Írj globális getIntDistribution függvényt, ami egy [min, max) balról zárt, jobbról nyitott intervallumon lévő számot ad vissza!

• Az első paramétere bármilyen RandomGenerator lehessen,
• második és harmadik paramétere pedig a [min, max) intervallum határai!

Az intervallum skálázását így érdemes megoldani:

Feltételezheted, hogy a maximális érték mindig nagyobb az intervallum hosszánál. Ez a módszer nem produkál egyenletes eloszlást, de ezzel most ne foglalkozzunk.

int getIntDistribution(RandomGenerator& rng, int a, int b) {
    return (rng.next() % (b-a)) + a;
}

Írj shuffleString nevű globális függvényt, ami Fisher-Yates algoritmussal összekever egy std::string-et!

• Az első paramétere bármilyen RandomGenerator lehessen,
• a második paramétere pedig az std::string, amit helyben összekever (megváltoztat)!

A Fisher-Yates algoritmus elve:

• a sztringen hátulról megy végig,
• az utolsó kivételével minden karakterét megcseréli
• az előtte lévő karakterek valamelyikével, akár önmagával.

Az std::string két, számunkra fontos művelete:

• ugyanúgy indexelhető, mint egy tömb,
• a mérete lekérdezhető a .size() tagfüggvénnyel.

void shuffleString(RandomGenerator& rng, std::string& str) {
    for (int i = str.size() - 1; i > 0; --i) {
        int r = getIntDistribution(rng, 0, i+1);
        char temp = str[r];
        str[r] = str[i];
        str[i] = temp;
    }
}

A RandomGenerator osztályhoz adj egy nextDouble() tagfüggvényt, ami a next() felhasználásával [0, 1) közötti valós számot generál! Vigyázz, a next() által visszaadott legnagyobb szám is változik az egyes generátoroknál!

class RandomGenerator {
public:
    // ...

    double nextDouble() {
        return next() / ((double) max() + 1.0);
    }
};

Írj a getIntDistribution-höz hasonló getDoubleDistribution függvényt, ami valós számot generál a valósakkal megadott intervallumon! Használd a nextDouble() függvényt, az intervallum skálázásához segít az ábra:

double getDoubleDistribution(RandomGenerator& rng, double a, double b) {
    return rng.nextDouble() * (b-a) + a;
}

A C++11 sokkal fejlettebb eszközöket szabványosított a random számok generálásához. Az egyik ilyen osztály a <random>-beli std::mt19937, ami egy 32 bites Mersenne twistert valósít meg.

• A következő random számot a függvényhívás operátorával tudjuk tőle kérni,
• van seed() nevű tagfüggvénye, amivel beállíthatjuk a seed-et,
• és van statikus max() függvénye, ami visszaadja a legnagyobb generálható számot.

Írj egy Cpp11Random osztályt, ami egy ilyen Mersenne twistert használ!

A seed "véletlenszerű" beállítása is különbözhet az egyes generátorokban:

• CRand és MSRand esetén nincs jobb lehetőségünk a Prog1-en megismert time(NULL) függvénynél,
• a Mersenne twistert azonban a szintén C++11-es std::random_device használatával szokás inicializálni. Olvass utána, hogyan kell használni!

Írj set_random_seed() függvényt, ami beállítja a seedet, és a hívónak vissza is tér az új seeddel! Ez arra lehet jó, hogy el lehessen menteni, hogy később újra lehessen játszani ugyanazt a játékot.