1iai1

Z Pascal
Prejsť na: navigácia, hľadanie

Cviko 30.4.2013

Projekt

Ak už máte zvolenú tému projektu, pošlite mi ju mailom s predmetom tema projektu.

NDÚ 8 (Algoritmy na grafoch)

Máme neorientovaný graf reprezentovaný poľom množín súsedov.

  • Napíšte metódu, ktorá zistí, či sa neorientovaný graf dá nakresliť jedným ťahom (dá sa vtedy, ak je súvislý a všetky vrcholy sú párneho stupňa alebo práve dva vrcholy sú nepárneho stupňa). Stupeň vrchola je počet vrcholov, s ktorými daný vrchol susedí.
  • Napíšte metódu, ktorá vypíše všetky vrcholy v najväčšom komponente grafu (čo sa týka počtu vrcholov). Ak je takých komponentov viac, stačí vypísať vrcholy jedného z nich.
  • Napíšte metódu, ktorá zistí, či graf obsahuje taký vrchol, po ktorého odstránení (vrátane hrán) by sa zvýšil počet komponentov grafu.

Môžete využiť program z cvičenia vrátane zadaných grafov v textových súboroch, ale Váš program musí fungovať pre ľubovoľný neorientovaný graf.

Vyriešenú úlohu pošlite do 30.4.2013 do 8:00. Úloha je za 1 bod.

Výsledky rozcvičiek

Rozcvičky označené x sa do súčtu bodov nepočítajú.

Meno1.2.NDU13.NDU24.NDU35.NDU46.NDU57.NDU68.NDU79.NDU810.NDU911.NDU1012.spolutéma projektu
Benčko Dominik 3,5 5 1 4,5 1 1,5    0,5 3,5   0,5 1 4,5     5      31,5  
Bohumel Branislav 5 3 1 2 0,5 x1,8 0,5 2 1 5  x1 1 4,5   4,5   4      34  
Brojo Roman 4,5   1 3,5   4,5   4 1 5  x0,5  1   3 1 2,5      31  
Burcl Marek 5 3 1 3,7   2,5  x0  1   1 1 x0,5 1 1 1 5      26,2  
Dúc Jozef 5 3,5 1 4 1 3,5 1 x2,5 1 5   3 1 x2,5 1 3,4   5      38,4 Policajná evidencia zločincov
Gerbóc Štefan  1 1 5   2,5 0 0   3,5    1 4     5      23  
Hoľa Michal 5 3,5 1 2,8 1 4,8 1 x1,5 1 5 1 2  x0  5 0,3 4      37,4 Malá škola
Hornáčková Barbora 5   1 4 1   1 4   5 1 3 1 5   4,9   5      40 Evidencia ubytovní v Európe
Lamoš Rastislav 4 1 1 5      1 5   1,5   3,5 1 3 1 2      29 Evidencia neplatičov
Lukáč Dominik 5 4,7   5   4,8   4   5  x4 1 x3,5 1 4,9   5      40 PNS
Masár Branislav 3,5 3,2 1 4 1 3,8 1 x0 1 3,5 1 2,5 1 x0,5 1 3 1 5      36,5  
Michalík Eduard 5 4,5 1    5   4 1 5  x2  4,5 1 3   4      38 Zoo
Opial Marián 5 3,2 1 5 1 2,3 1 4 1 5 1 x1,5 1 x1 1 4,5   5      40  
Rückschloss Lukáš 5 2,5   4,5   4,5  x0  5   3   4   3        31,5  
Smolíková Katarína 5 5  x3,2  3,8   5   4  x1 1 4,5   4,8   4      37,1  
Straka Martin  2,5 1   1 1 1 0     0 1 3          10,5  
Stuchlík Martinx3,5 5 1 5 1 5 1 5 1 5 1 3,5 1 3,5 1 4,9 1 x2,5     40 Múzeum
Šišková Patrícia 5 4,5 1 5 1 2,5 1 0     2,5 1 4,5 1 3,5 1 5      38,5  
Šultys Jakub 5 4 1 3,8                    13,8  
Vališová Karin 4 5 1 5 1 4,9 1 2,5 1 4,8 1   1 4,5     5      40 Dinosaury

Aktualizované: 30. 4. 2013

Staršie NDÚ

NDÚ 7 (Grafy) Pre graf reprezentovaný dynamickým poľom dynamických polí definujte metódy na vykreslenie vrchola (krúžok s jeho indexom alebo menom), hrany (v prípade ohodnoteného grafu sa do stredu hrany vypíše jej váha) a celého grafu.

Naprogramujte zadávanie vrcholov a hrán grafu klikaním do grafickej plochy (Image1MouseDown)

  • kliknutie na prázdne miesto plochy pridá nový vrchol (nakreslí krúžok)
  • kliknutie na existujúci vrchol ho zafarbí
  • kliknutie na druhý ešte nezafarbený vrchol ho spojí so zafarbeným (ak už bolo spojenie, tak rozpojí)
  • kliknutie na zafarbený vrchol ho odfarbí

NDÚ 6 (RadixSort) Naprogramujte triedenie RadixSort (postup triedenia máte popísaný v 30. prednáške). Môžete si zvoliť či budete tirediť pole čísel, spájaný zoznam čísel alebo binárny súbor čísel. V testovacej aplikácii vypište čísla na začiatku (ešte neutriedené) a potom po každom zlúčení kôpok do jednej postupnosti.

NDÚ 5 (Aritmetický/Lexikografický strom) Vyberte si práve jeden z príkladov 1,2.

  1. Definujte konštruktor (alebo funkciu), ktorý vytvorí aritmetický strom na základe prefixu (vstupný parameter). Čísla v prefixe môžu byť aj viacciferné a sú navzájom oddelené aspoň jednou medzerou. V aplikácii na testovanie strom aj vyhodnoťte (máte v prednáške).
  2. Definujte nasledujúce metódy triedy TLexStrom:
    • funkcia PocetVyskytov(Slovo:string):integer, ktorá zistí počet výskytov slova Slovo
    • funkcia SlovaDlzky(Dlzka:Integer):string, ktorá vráti reťazec slov v strome s danou dĺžkou (môžte definovať aj ako procedúru, ktorá slová danej dĺžky postupne niekam vypíše, no nemusí ich zbierať do jedného reťazca)
    • funkcia Najcastejsie:string, ktorá vráti najfrekventovanejšie slovo v strome

Môžte použiť už hotové programy z prednášky či cvík. Vytvorte aplikáciu na otestovanie (môže byť konzolová alebo grafická).

NDÚ 4 (binárny strom) Definujte konštruktor triedy Tstrom - Create(Preorder, Inorder: string), ktorý skonštruuje celý strom (vo vrcholoch sú znaky), ktorého parameter Preorder je preorderovský výstup a Inorder je inorderovský výstup. Môžte počítať s tým, že v žiadnom reťazci sa znaky neopakujú.

Na otestovanie vytvorte konzolový program, ktorý od používateľa načíta 2 reťazce, potom skonštruuje strom a vypíšte ho preorderom aj inorderom. Uvedomte si, že program nemôžte testovať na ľubovoľnej kombinácii 2 reťazcov (teda ak si vymyslíte preorder, inorder už nemôže byť ľubovoľná permutácia tých istých znakov, iba niektoré permutácie sú dobré).

NDÚ 3 (spájaný zoznam)

V textovom súbore slovnik.txt je v každom riadku 1 slovenské slovo a jeho anglický predklad - oddelené medzerou. V samostatnom unite definujte triedu TSlovnik (ako spájaný zoznam), ktorá bude slúžiť na prácu so slovníkom. Triedu môžete zadefinovať napr. takto. Vrcholy v zozname stále udržiavajte utriedené podľa anglických slovíčok. Definujte metódy, ktoré umožnia:

  • načítať zoznam z daného textového súboru (meno súboru v parametri).
  • vyhľadať slovenský preklad zadaného anglického slova
  • uložiť slovník do daného textového súboru (meno súboru v parametri)

Na otestovanie metód vytvorte program (stačí konzolový), ktorý

  • načíta slovník zo súboru slovnik.txt
  • načíta (z konzoly) anglické slovo a vypíše jeho slovenský preklad. Ak sa v slovníku nenachádza, vypíše o tom správu.
  • načíta anglické slovo, potom jeho slovenský preklad a dvojicu pridá do slovníka (ak tam ešte nie je)
  • zapíše takto zmenený slovník do súboru novy.txt.

Nepoužívajte žiadne pomocné polia, ani iné ako uvedené súbory.

NDÚ 2 (spájaný zoznam)

Definujte procedúru VyhodDuplikaty, ktorá vyhodí zo zoznamu všetky ďalšie výskyty tej istej hodnoty. Napr. zoznam 1->4->7->4->5->8->6->7->4->9->5->nil zmení na zoznam 1->4->7->5->8->6->9->nil. Kvôli testovaniu definujte tiež procedúry na načítanie zoznamu z textového súboru, výpis zoznamu a uvoľnenie zoznamu. Nepoužívajte žiadne pomocné polia ani súbory.

NDÚ 1 (údajový prúd)

Zadanie nájdete na stránke s cvičením.