C++ Gyakorlás

Ezen az oldalon próbálok összegyűjteni (idővel) különböző gyakorló feladatokat C++ programozásból. Lesz köztük néhány egészen könnyű, de akadhatnak komoly, sok időt igénybe vevő feladatok, amelyek megoldása akár még használható is lehet valamire a gyakorlatban.
Guess
Nehézség: könnyű

Írj egy programot, amely legfeljebb 10 kérdésből kitalálja, hogy a felhasználó milyen számra gondolt 1 és 1000 között! (És ha nem találja ki, írja ki, hogy a felhasználó egy csaló! :D)

Palindrome
Nehézség: könnyű

Írj egy programot, amely soronként olvas a standard inputról, és minden sorról eldönti, hogy palindróma-e. (Olyan szöveg, amely visszafele olvasva ugyanaz.)

DoubleArray
Nehézség: normál

Írj egy DoubleArray osztályt, amely egy double-ket tároló flexibilis tömböt valósít meg.

A flexibilis tömbök lényege, hogy méretük futás közben igény szerint változhat. Ezt dinamikus memóriával lehet megvalósítani. Amikor létrejön egy új példány, akkor fix számú cellát lefoglalunk. (pl. 8) Ezek után amíg a felhasználó 9-nél kevesebb elemet adott a tárolóhoz, nem kell hozzányúlnom a memóriához. Amint teli tárolóhoz próbálok hozzáadni elemet, lefoglalok egy nagyobb tömböt, átmásolom az eddigi elemeket az új tömbbe, felszabadítom a régit, és haladok tovább. Általában ezt úgy szokták megvalósítani, hogy az újonnan lefoglalt tömb valamilyen konstansszorosa az előző tömb méretének. (Így lineáris növekedés esetén csak logaritmikus mennyiségű újrafoglalásra van szükség.)

Úgy tudom, hogy gcc-nél 2 szokott lenni a szorzó, amit az std::vector használ, Microsoft Visual C++-nál pedig 1.5

Az osztály valami efféle kell, hogy legyen:

DoubleArray.hpp
class DoubleArray {

    private:
        // dinamikusan foglalt tarterulet
        double* memory_;
        // dinamikusan foglalt terulet elemszama
        unsigned memory_size_;
    public:
        DoubleArray(); // ures tomb letrehozasa

        DoubleArray(const DoubleArray& other); // masolas

        ~DoubleArray(); // destruktor

        unsigned
        count() const; // aktualis elemszam lekerdezese

        void
        add(double x); // uj elem hozzaadasa a tomb vegehez

        void
        set(unsigned index, double value); // elem modositasa

        double
        get(unsigned index); // elem lekerdezese

        void
        erase(unsigned index); // elem torlese

};
IncludeSearch
Nehézség: normál

Írj egy programot, amely parancssori argumentumként kaphet tetszőleges számú forrásfájlt, és megkeresi, hogy ezek a fájlok mely fájlokat includeolják. Az eredményt minden fájlhoz kiírják a standard outputra. A program csak az idézőjellel includeolt fájlokat keresse!

Javasolt referencia: string

Példa a használatra:

$ ./IncludeSearch foo.cpp bar.cpp

foo.cpp: foo.hpp, bar.hpp, asdasd.hpp
bar.cpp: bar.hpp

A dolog lényege, hogy soronként olvashatom a fájlokat, hiszen a C/C++ preprocesszor is sor-alapú. Egy sor akkor lesz számomra érdekes, ha az első nem-whitespace karaktere kettőskereszt (#). A kettőskereszt után állhat tetszőleges számú (akár nulla) whitespace karakter, majd az include szó kell, hogy kövesse. Az include után megint tetszőleges számú whitespace, majd idézőjelet keresek. Ha ez megvan, akkor a sor végéig olvasok. Természetesen a záró idézőjel nem érdekes, viszont elvárjuk, hogy legyen. (Különben hibás az adott input fájl, így nem írunk vele kapcsolatban semmit az outputba.) Ennyi, egyszerűen ki kell szednünk, hogy milyen #include "..." sorok találhatóak.

Az igazán szép megoldások az egyes fájlokban includeolt többi fájl nevét egy halmazba teszik, így ha egy fájl többször includeol valamit, az akkor sem kerül kétszer az outputba. (set<string>)

RecursiveIncludeSearch
Nehézség: nehéz

A feladat előfeltétele az IncludeSearch (előző példa) elkészítése

Fejlesszük tovább az előző programot: A beadott forrásfájlok includejaira is futtassuk automatikusan az include keresőt, ezzel újabb output sorokat generálva. Tehát megtaláljuk az includeok includejait is, és azok includejait, stb...

Egy lehetséges példa: A foo.cpp includeolja a foo.hpp-t, ami includeolja a doo.hpp-t. A foo.cpp közvetlenül nem includeolja a doo.hpp-t, mégis rejtve, a foo.hpp-n keresztül függ tőle. Emiatt érdemes volna a foo.hpp függőségeit is figyelembe venni. Output (egy kicsit bonyolultabb példára):

$ ./RecursiveIncludeSearch foo.cpp
foo.cpp: foo.hpp
foo.hpp: doo.hpp
doo.hpp: bar.hpp, baz.hpp
bar.hpp: baz.hpp
Ezzel sikerült meghatároznunk, hogy a foo.cpp fordítása során milyen fájlok kerülnek feldolgozásra. Ez a kimenet már kódolja a foo.cpp összes függőségét is.
IncludeGraph
Nehézség: nehéz

A feladat előfeltétele a RecursiveIncludeSearch (előző példa) elkészítése

Fejlesszük tovább az előző programot! Most írjuk ki minden forrásfájlhoz, hogy mely fájloktól függ! (Ez az előző példában előálló gráf tranzitív lezártja lesz.) Az előző példa outputja ezzel a programmal:

$ ./IncludeGraph foo.cpp
foo.cpp: foo.hpp, doo.hpp, bar.hpp, baz.hpp
foo.hpp: doo.hpp, bar.hpp, baz.hpp
doo.hpp: bar.hpp, baz.hpp
bar.hpp: baz.hpp

A -r kapcsolóval pedig a transzponált tranzitív lezártját írjuk ki! (Tehát azt, hogy melyek azok a fájlok, amelyek egy adott fájltól függenek)

$ ./IncludeGraph -r foo.cpp
baz.hpp: bar.hpp, doo.hpp, foo.hpp, foo.cpp
bar.hpp: doo.hpp, foo.hpp, foo.cpp
doo.hpp: foo.hpp, foo.cpp
foo.hpp: foo.cpp