Szorgalmi feladatok

A feladatok megoldásai az admin portálon adhatók be. A szorgalmi feladatokkal egy pontversenyben is részt lehet venni. Alapbeállítás szerint anonim módon jelensz meg a táblázatban. Ha szeretnél névvel megjelenni vagy teljesen eltűnni, az admin portálon beállíthatod.

A verseny állásának megtekintéséhez is be kell jelentkezni.

Teljes tört osztály

Dolgozd ki az előadáson bemutatott kódot folytatva a teljes tört osztályt C++ nyelven!

Valósítsd meg a + (egyoperandusú), +=, - (egy- és kétoperandusú), -=, *, *=, /, /=, >>, (double) cast operátorokat! Figyelj a referenciák helyes használatra!

Mennyi a legkevesebb új tagfüggvény (szintaktikai értelemben), amennyivel ez megoldható? Oldd meg úgy a feladatot, hogy a lehető legkevesebb legyen!

Figyelj arra, mit jelentenek az „egyoperandusú” és „kétoperandusú” szavak! Ezek nem az operátorokat megvalósító függvények paraméterszámát adják meg. Például egyoperandusú mínusz az ellentett: -x, és kétoperandusú mínusz a kivonás: a-b. Egyoperandusú csillag a dereferálás: *p, kétoperandusú csillag a szorzás: a*b.

Elfogadott megoldások: 10 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-09-14 04:00:00.

Készítsed el a https://cpp11.eet.bme.hu/f00/#1 1. Morzekódot dekódoló tömb feladatot.

Elfogadott megoldások: 8 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-09-21 04:00:00.

Függvény osztály

Az előadás kifejezésfáival kapcsolatos feladat.

Tervezz és implementálj egy általános függvény osztályt! Hova illik ez be az osztályhierarchiába? Implementálj egy szinusz és egy koszinusz osztályt! Ha ügyesen tervezted meg a függvény osztályt, akkor ezek az összeghez és a szorzathoz hasonlóan pár sorból fognak állni.

Ha kész vannak a függvény, szinusz és koszinusz osztályok, akkor most írd meg azok deriválását is! Figyelj arra, hogy az összetett függvény deriválási szabályát kell alkalmaznod: f(g(x))'=f'(g(x))·g'(x), mert a szinusz vagy a koszinusz objektum is egy kifejezést tartalmaz.

Használd a függvénysablon tervezési mintát! Próbáld meg a függvény osztályban megvalósítani, amit csak lehet, hogy a leszármazottak minél egyszerűbbek legyenek. Onnan tudod, hogy jó a megoldásod, hogy a függvény ősosztály deriváló metódusa a láncszabályt tartalmazva final minősítőt kaphat (és csak ilyen megoldásra jár majd pont). Ugyanez a helyzet a print metódussal.

Elfogadott megoldások: 14 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-09-28 04:00:00.

Ha megcsináltad a sztringes házihoz tartozó szorgalmit (csak az egyiket, vagy akár mind a kettőt), azt ide töltheted fel plusz pontért.

Elfogadott megoldások: 10 darab.
Szerezhető: 2 pont. Leadási határidő: 2026-11-01 23:59:00.

Hanoi tornyai

Adott az alábbi forráskód, amely a Hanoi tornyai feladványt oldja meg:

#include <iostream>

void hanoi(int n, char honnan, char seged, char hova) {
    if (n == 0)
        return;
    hanoi(n-1, honnan, hova, seged);
    std::cout << "rakj 1-et: " << honnan << "->" << hova << std::endl;
    hanoi(n-1, seged, honnan, hova);
}

int main() {
    hanoi(4, 'A', 'B', 'C');

    return 0;
}

Hogy lehet megoldani azt, hogy minden lépés mellé ki legyen írva annak sorszáma? Pl. 3 korongra így:

1. lepes: rakj 1-et: A->C
2. lepes: rakj 1-et: A->B
3. lepes: rakj 1-et: C->B
4. lepes: rakj 1-et: A->C
5. lepes: rakj 1-et: B->A
6. lepes: rakj 1-et: B->C
7. lepes: rakj 1-et: A->C

Mutass minél többféle, egymástól eltérő elvű (nem csak szintaktikailag különböző) megoldást! A rekurzió maradjon meg. Mi a megoldásokban a közös?

Figyelj arra, hogy az elkészített függvények használatának módja – lényegében a fejléce – ugyanaz legyen, mint az eredeti függvényé (korongok száma, oszlop1, oszlop2, oszlop3)! Ez persze nem jelenti azt, hogy nem írhatsz segédfüggvényeket ettől eltérő paraméterezéssel. Ne csinálj tárolót, nincs rá szükség: a függvény olyan sorrendben állítja elő a lépéseket, ahogy a kimenetre is azoknak kerülniük kell.

Van két olyan „triviális” módszer, ami nélkül a beküldött kód nem lesz elfogadott. Sajnos ezek nem specifikálhatóak, mert ha a feladatkiírásban szerepelnének, akkor az a megoldást is elárulná egyből. Egyszerűségük miatt sejteni fogod, amikor megtaláltad őket, hogy ezekről van szó. Ha nem, számíts „találj ki még más elvű megoldást” értékelésre. Lásd az előadást is!

Elfogadott megoldások: 15 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-10-05 04:00:00.

Számrendszerek

Nézd meg az extrákban az I/O manipulátorokkal kapcsolatos írást! Ez az előadás mértékegységes példájának folytatása. Utána...

a) Írj bináris szám kiíró I/O manipulátort! A használata legyen az alábbi:

std::cout << bin << 0 << std::endl;         /* 0 */
std::cout << bin << 240 << std::endl;       /* 11110000 */

Vajon mi lehet itt a bin típusa?

b) Írj akárhányas számrendszerben kiíró I/O manipulátort!

std::cout << base(2) << 240 << std::endl;   /* 11110000 */
std::cout << base(7) << 240 << std::endl;   /* 462 */
std::cout << base(16) << 240 << std::endl;  /* F0 */

Melyik az első részkifejezés, amit ki kell értékelnie a fordítónak? Indulj ki ebből!

Ügyelj arra, hogy a megvalósításban ne legyen pow() (egész számokkal kell dolgozni, a pow() pedig lebegőpontos számokkal dolgozik, pontatlanság lehet). Ezen kívül, ne legyen std::to_string() se! Legalábbis egyetlen számjegy sztringgé alakítására semmiképp, mivel akkor minden számjegyhez külön std::string objektum jönne létre. Általában véve, mindenféle dinamikus memóriakezelést elkerülhető.

Elfogadott megoldások: 11 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-10-19 04:00:00.

A range-based for ciklus kényelmesen bejárja egy tároló elemeit, ám önmagában nem adja meg, hogy az aktuális elem hányadik a bejárásban. Például:

std::list<std::string> nevek = {"Anna", "Béla", "Csilla"};
for (auto const& nev : nevek)
    std::cout << nev << '\n';

Külön számlálóváltozóval követhetnénk az elemek sorszámát, de ezt egy iterátoradapter is megoldhatja: minden bejárt elemhez hozzárendel egy indexet.

Pythonban az enumerate() segítségével egyszerre kapható meg a sorszám és az elem:

nevek = ["Anna", "Béla", "Csilla"]
for sorszam, nev in enumerate(nevek):
    print(sorszam, nev)

Kimenet:

0 Anna
1 Béla
2 Csilla

A Boost.Range könyvtár indexed() adaptere hasonló funkciót nyújt C++-ban:

using namespace boost::adaptors;
for (auto const& elem : nevek | indexed(0))
    std::cout << elem.index() << ' ' << elem.value() << '\n';

Az indexed() paraméterével a kezdő sorszám is megválasztható; az index tehát nem feltétlenül a tárolóban tárolt pozíciót jelenti. Ez például std::list esetén is használható, ahol nincs indexelési operátor.

Feladat

Készíts C++ iterátoradaptert, amely egy tároló bejárásakor az elem értéke mellett egy sorszámot is szolgáltat!

Az alábbi megoldási lehetőségek közül választhatsz:

• Az adaptert függvényhívással (például enumerate(tarolo, kezdoindex)) vagy a Boost mintájára | operátorral lehessen létrehozni.
• Az index és az elem elérését biztosíthatod .index() és .value() tagfüggvényekkel, vagy egy std::pair két tagjával (.first és .second).
• Az index kezdőértékét lehessen megadni, így a számozás ne csak nulláról indulhasson.

A std::pair-t alkalmazó változat egyik lehetséges használati módja:

std::list<std::string> nevek = {"Anna", "Béla", "Csilla"};
for (auto par : enumerate(nevek, 0))
    std::cout << par.first << ' ' << par.second << '\n';

Elvárt kimenet:

0 Anna
1 Béla
2 Csilla

Elfogadott megoldások: 12 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-10-26 04:00:00.

Összefésülő rendezés

Az összefésülő rendezés (merge sort, lásd Prog1/Algel, https://preview.redd.it/ke79d99ynaz11.png?auto=webp&s=6563c537f3098e81c614c6284cd39628e4151d9e) lényege a következő:

• Rekurzívan rendezzük a tömb első és második felét.
• Ezek után pedig a két különálló, rendezett tartományt összefésüljük egyetlen rendezett tartománnyá.

Alább egy megvalósítás int-ek tömbjére.

void merge(int *in, int begin, int mid, int end, int *out) {
    int i = begin, j = mid;
    for (int c = begin; c < end; ++c) {
        if (i < mid && (j >= end || in[i] <= in[j])) {
            out[c] = in[i];
            i++;
        } else {
            out[c] = in[j];
            j++;
        }
    }
}

void copy(int *in, int begin, int end, int *out) {
    for (int c = begin; c < end; ++c) {
        out[c] = in[c];
    }
}

void merge_sort(int *tomb, int begin, int end, int *temp) {
    if (end - begin < 2)
        return;
    int mid = (begin + end) / 2;
    merge_sort(tomb, begin, mid, temp);
    merge_sort(tomb, mid, end, temp);
    merge(tomb, begin, mid, end, temp);
    copy(temp, begin, end, tomb);
}

Az összefésüléshez szükséges egy segédtömb: a két fél tartomány az összefésülés (merge) során a segédtömbbe kerül, ahonnan aztán vissza kell másolni (copy). A fenti rendező függvény ezért elvárja a hívójától, hogy kapjon egy munkaterületet, amelyik az eredeti tömb méretével megegyező méretű.

Végezd el az alábbi módosításokat a kódon!

• Template-esítsd: ne inteken dolgozzon, hanem tetszőleges típusú elemeken. Természetesen a <, >= stb. operátorokat attól a típustól elvárhatod.
• Csinálj egy csomagoló függvényt, amely lefoglalja magától a megfelelő méretű segédtömböt, hogy ezzel ne a hívónak kelljen bajlódnia!
• Figyeld meg, hogy az összefésülésnél a segédtömbbe MÁSOLÓDNAK az objektumok, aztán onnan az eredeti helyükre visszaMÁSOLÓDNAK megint. Ezeknek a lépéseknek nem másolásnak, hanem mozgatásoknak kellene lenniük. Alakítsd át úgy a kódot, hogy (1) a segédtömb inicializálatlan memóriaterület legyen, amelyre (2) az összefésülés átmozgatja az objektumokat, és ahonnan végül a lecserélt copy függvény (3) az eredeti tömbbe, a végleges helyükre visszamozgatja azokat!

Figyelj arra, hol használsz konstruktort, destruktort és értékadást! A megoldásod az extrák menüpont alatt elérhető SuperNoisy osztállyal is tesztelheted. Figyelj arra, hogy a rendezendő tömb elemeinek lehet, hogy nincs default konstruktora!

Elfogadott megoldások: 10 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-11-02 04:00:00.

Mérési adatok feldolgozása

Egy mérőberendezésből érkező adatokat több lépésben kell feldolgozni. Az egyes feldolgozási lépések eltérő műveleteket valósítanak meg: eltolhatják a mért értéket, korlátozhatják a változását, vagy az eddigi értékekből átlagot számolhatnak.

A feldolgozási lépéseket különböző osztályok írják le. Ezek az osztályok nem állnak öröklési kapcsolatban egymással, viszont mindegyiknek van double operator()(double) művelete.

Például:

struct Eltolas {
    double delta;

    explicit Eltolas(double d) : delta(d) {}

    double operator()(double x) {
        return x + delta;
    }
};

class FutoAtlag {
    double osszeg = 0.0;
    unsigned darab = 0;

public:
    double operator()(double x) {
        osszeg += x;
        return osszeg / ++darab;
    }
};

Az Eltolas minden bemeneti értékhez hozzáad egy állandót. A FutoAtlag az eddig hozzá érkezett bemeneti értékek átlagával tér vissza. Az utóbbi működése a korábbi hívásaitól is függ.

Feladat

Valósítsd meg a MeresiProgram osztályt, amelybe tetszőleges számú feldolgozási lépés helyezhető el!

• A hozzaad() tagfüggvénnyel egy új lépés illeszthető a program végére. Fogadjon el tetszőleges másolható objektumot, amelyen meghívható a double operator()(double) művelet.
• A feldolgoz(double) sorban végrehajtja a tárolt lépéseket. Egy lépés eredménye a következő bemenete. A végső eredményt adja vissza.
• Ha nincsenek lépések, a feldolgoz() az eredeti bemeneti értéket adja vissza.
• A MeresiProgram legyen másolható és értékül adható. Másoláskor a lépések aktuális belső állapota is másolódjon át.
• A másolt programok legyenek teljesen függetlenek: az egyik későbbi feldolgozásai ne változtassák meg a másik állapotát.
• Minden eltárolt objektum megfelelően szűnjön meg; a MeresiProgram használható legyen std::vector<MeresiProgram> elemeként is.

Elvárt működés

Az alábbi kódrészletnek működnie kell (a megfelelő fejléceket is be kell illeszteni):

MeresiProgram p;
p.hozzaad(Eltolas{1.0});
p.hozzaad(FutoAtlag{});

assert(p.feldolgoz(1.0) == 2.0); // az atlagolo a 2-t kapja
assert(p.feldolgoz(3.0) == 3.0); // a 2 es a 4 atlaga

MeresiProgram q = p;              // az atlagolo allapota is masolodik

assert(p.feldolgoz(5.0) == 4.0); // (2+4+6)/3
assert(q.feldolgoz(8.0) == 5.0); // (2+4+9)/3

Megkötések

1. A feldolgozási lépések osztályait nem szabad módosítani, és nem követelhető meg tőlük közös ősosztály vagy további tagfüggvény.
2. Nem használható std::function és std::shared_ptr.
3. A programok másolása ténylegesen másolja át a lépések állapotát; közös állapot használata nem megengedett.

A megoldást teszteld legalább kétféle feldolgozási lépéssel, programok másoló konstruktorával, értékadásával, valamint üres programmal. Javasolt egy olyan osztályt is kipróbálni, amelynek a példányai módosítják a saját állapotukat a függvényhívó operátorban.

Elfogadott megoldások: 0 darab.
Szerezhető: 2 pont. Leadási határidő: 2026-11-16 04:00:00.

SmallVector

Short string optimization

A legtöbb fordító által implementált std::string használ egy nagyon fontos optimalizálást: rövid sztringek esetén egyáltalán nem használ dinamikus memóriát, hanem van erre egy karaktertömb adattagja.

Ezzel rengeteget lehet gyorsítani, a valóságban ugyanis a sztringek túlnyomó többsége tényleg igen rövid, akár a sztringek 90-95%-a beleférhet max. 15 karakterbe.

A trükk azzal egészül ki, hogy ehhez még az objektumok méretét sem kell növelni! Ha elképzelünk egy egyszerű, okosan nyújtózkodó dinamikus tömböt:

class String {
    char* data_;
    size_t size_;
    size_t capacity_;
};

Feltűnhet, hogy ha emellé felvennénk egy 16 elemű karaktertömböt, akkor size_ <= 15 esetén a data_ és a capacity_ adattagok feleslegessé válnak: mindig vagy azok, vagy a karaktertömb van használatban, a kettő egyszerre sosem.

Erre már C-ben is volt trükk, a union, aminek mindig csak az egyik adattagja aktív, és a használatánál nekünk kell tudni, hogy melyik.

class String {

    struct Long {
        char* data_;
        size_t capacity_;
    };

    union Storage {
        Long long_;
        char short_[16];
    }

    size_t size_;
    Storage storage_;
};

Így ha 64 bites rendszeren fordítjuk a kódot, akkor a sizeof(String) ugyanúgy 24, mint előtte, viszont már sokkal kevesebbszer használ dinamikus memóriát.

Feladat

Ezt az ötletet felhasználhatjuk más tárolókhoz is, nem csak sztringekhez. Készíts SmallVector osztálysablont, aminek megadhatjuk, hány elemet tároljon stacken! Ha ennél több elemet akarunk tárolni, akkor térjen át a haladó dinamikus memóriakezelésre.

Ebben a feladatban nem kell a union trükk, a lényeg az, hogy helyesen kezeld a tartalmazott objektumok életciklusát, hasonlóan, mint az optional. Ezeket kell tudnia:

• default konstruktor,
• másoló és mozgató konstruktor,
• destruktor,
• data() size() és indexelés,
• reserve() és másoló push_back(),
• az értékadó operátorokat nem kell megírnod, elég, ha törlöd.

Elfogadott megoldások: 2 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-11-09 04:00:00.

Noexcept függvények

A főprogramban két kódrészlet van. Külön kell őket vizsgálnod. Melyiknél mi történik? Miért?

#include <iostream>

struct X {
    X() = default;
    X(X const &) { throw 0; }
};

void f_val(X param) noexcept {
}

void f_ref(X const & param) noexcept {
    X copy(param);
}

int main() {
    X x1;

    try {
        std::cout << "f_val hivasa" << std::endl;
        f_val(x1);
    } catch (...) {}

    try {
        std::cout << "f_ref hivasa" << std::endl;
        f_ref(x1);
    } catch (...) {}
}

Elfogadott megoldások: 0 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-11-16 04:00:00.

Noexcept mozgató konstruktor

Mi a hiba az alábbi programrészben? Kettőt is tudsz mutatni!

class String {
    /* ... */
};

String::String(String && moved) noexcept {
    data_ = moved.data_;
    len_ = moved.len_;
    moved.data_ = new char[1];
    moved.data_[0] = '\0';
    moved.len_ = 0;
}

Elfogadott megoldások: 0 darab.
Szerezhető: 1 pont. Leadási határidő: 2026-11-16 04:00:00.