10. Rozum do hrsti

Táto kapitola obsahuje niekoľko neriešených úloh resp. námetov pre samostatnú prácu. Každá z úloh vyžaduje použitie niektorej z dynamických údajových štruktúr, o ktorých sme hovorili v predchádzajúcich kapitolách. V prípade problémov či nejasností, odporúčam vrátiť sa k príslušnej kapitole resp. požiadať o radu skúsenejšieho kolegu - programátora alebo svojho učiteľa programovania. Určite sa poteší :-)

Veľa úspechov!

  Množiny sú reprezentované jednosmernými lineárnymi zoznamami svojich prvkov (každý prvok množiny je v zozname uložený práve raz, prvkami množiny sú celé čísla). Napíšte program, ktorý umožní zrealizovať operácie zjednotenia a prieniku dvoch množín.

Napr. pre dva vstupné zoznamy, z ktorých jeden obsahuje (v ľubovoľnom poradí) prvky 1, 3, 5, 6, 8 a druhý 2, 3, 4, 5, 6 bude v prípade zjednotenia výsledný zoznam obsahovať prvky (opäť v ľubovoľnom poradí) prvky 1, 2, 3, 4, 5, 6, 8 a v prípade prieniku zase prvky 3, 5, 6.

Vyriešte úlohu aj pre prípad, keď sú množiny reprezentované usporiadaným lineárnym zoznamom svojich prvkov.

  Vytvorte program kontrolujúci správnosť uzátvorkovania výrazu s využitím zásobníka. Vstupom programu nech je výraz - postupnosť znakov, ktorá môže obsahovať písmená anglickej abecedy, matematické operátory +, -, /, * a samozrejme zátvorky ( , ).

  Vytvorte program, ktorý vypočíta hodnotu xⁿ pre veľké prirodzené číslo x.

  Vytvorte program na výpočet členov Fibonacciho postupnosti pomocou posuvného registra.

Fibonacciho postupnosť: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

Rekurentný vzťah: F₀ = 0,  F₁ = 1,  F_i = F_i-1 + F_i-2   pre i >= 2

  Sú dané dva usporiadané zoznamy celých čísel. Napíšte program, ktorý z nich vytvorí jeden usporiadaný zoznam tak, že preradí číslo z konca prvého zoznamu na správne miesto do druhého zoznamu. Postup sa opakuje, až kým nevznikne jeden usporiadaný zoznam. Nie je možné použiť funkcie malloc ani free, výsledok musíte dosiahnuť len zmenami ukazovateľov v uzloch!

  Vytvorte program, ktorý bude simulovať pohyb guľôčky po "rulete". Zo súboru načítajte poradie políčok na rulete - pre každé políčko číslo a farbu (červená, čierna). Gulička môže byť na ruletu hodená ľubovoľným smerom, zastaví sa náhodne na niektorom políčku. Využite cyklický obojsmerný lineárny zoznam.

Vyriešte aj pre prípad, keď sú na rulete dve rôzne guličky pohybujúce sa opačnými smermi - keď sa stretnú, odrazia sa od seba a pokračujú v pohybe opačnými smermi ako pred nárazom.

  Implementujte zásobník a front ako jednorozmerné pole. Napíšte potrebné funkcie realizujúce jednotlivé operácie, ošetrite všetky "kritické" situácie - ako preplnenie zásobníka (frontu), snaha vybrať prvok z prázdneho zásobnika (frontu).

  Vytvorte program, ktorý umožní simulovať priebeh tenisového turnaja. Na vstupe prečítajte počet kôl. Vytvorte "turnajového pavúka" - úplný binárny strom potrebnej výšky a do listov uložte mená hráčov. V každom kole sa s dvojice hráčov na najnižšej úrovni stromu náhodne určí víťaz, ktorý postúpi do ďalšieho kola (v strome o úroveň vyššie). Po prebehnutí každého kola sa najnižšia úroveň stromu zruší. Zobrazujte priebeh turnaja na obrazovke tak, aby bolo možné sledovať, kto s kým hral a na konci oznámte meno víťaza celého turnaja.

Ak má turnaj 3 kolá - štvrťfinále, semifinále a finále - znamená to, že sa ho zúčastňuje 2³ = 8 kráčov.

  Napíšte program, ktorý bude analyzovať vstupný textový súbor. Vstupný súbor sa bude čítať po slovách (slovo chápeme ako postupnosť znakov pred a za ktorou je medzera alebo znak konca riadku) a prečítané slová sa budú ukladať do binárneho vyhľadávacieho stromu (tzv. lexikografický strom). Ak sa prečítané slovo nachádza v strome, zvýšime počet jeho výskytov, ak sa v strome zatiaľ nenachádza, pridáme ho na správne miesto. Na obrazovku sa vypíše tabuľka výskytov jednotlivých slov. Na požiadanie program zistí, či sa hľadané slovo nachádzalo v súbore.

  Napíšte funkciu, ktorá zabezpečí zobrazenie binárneho stromu na obrazovke v prehľadnej podobe (hodnoty vrcholov budú vhodne odsadené zľava podľa úrovní).