Vzorove zadanie leto 1

Z Pascal
Revízia z 10:10, 8. máj 2013; Andrej (Diskusia | príspevky)

(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
Prejsť na: navigácia, hľadanie

Ukážkové zadanie skúšky v letnom semestri



1. Farbenie komponentov

V binárnom súbore subor.dat (resp. subor1.dat, subor2.dat) sú uložené informácie o neorientovanom neohodnotenom grafe. Pre každý vrchol sú v ňom uložené súradnice X, Y v grafickej ploche a zoznam niekoľkých jeho susedov. Tento zoznam susedov je ukončený hodnotou -1. Súbor pozostáva z postupnosti blokov o samotných vrcholoch grafu, pričom prvý blok popisuje 0-tý vrchol, druhý blok 1-vý vrchol, ... Každý takýto blok obsahuje:

  • dve celé čísla X a Y - súradnice
  • postupnosť celých čísel - zoznam čísel susediacich vrcholov
  • blok je ukončený celočíselnou hodnotou -1

Keďže graf je neorientovaný, ak je v súbore definovaná hrana z vrcholu A do B, tak musíte dodefinovať aj hranu z B do A. Môžete predpokladať, že súbor je zadaný korektne a tiež, že graf neobsahuje viac ako 256 vrcholov.

Tento graf prečítajte zo súboru a farebne označte vrcholy tak, aby vrcholy toho istého komponentu boli zafarbené rovnakou farbou – každý komponent by mal byť zafarbený inou farbou. Ak by mal mať graf viac ako 10 komponentov, niektoré rôzne komponenty môžu mať rovnaké zafarbenie (stačí mať pripravených 10 rôznych farieb).

Pri štarte programu sa vykreslí načítaný a zafarbený graf a čaká sa na klikanie na vrcholy grafu. Ak používateľ klikne na ľubovoľné dva vrcholy, tak sa pre ne zmení ich vzájomný vzťah: ak boli spojené hranou, tak táto sa zruší, ak medzi nimi zatiaľ hrana nebola, tak sa vytvorí. Po každej takejto zmene grafu (pridanej alebo zrušenej hrane) sa graf prekreslí s novým zafarbením komponentov (zrejme farby sa zmenia, len ak sa zmenil počet komponentov).

Graf zadefinujte v unite GrafUnit, pričom ako riešenie skúšky budete odovzdávať len tento jeden unit. V tomto unite nepoužívajte žiadne globálne premenné.

Použite tento projekt ako základ vášho riešenia.


2. Labyrint

V textovom súbore labyrint.txt (resp. labyrint1.txt, labyrint2.txt) máme zadefinovaný labyrint, ktorý je definovaný v štvorčekovej sieti takto:

  • steny labyrintu sú zapísané znakom *;
  • medzery vyjadrujú políčka, cez ktoré sa dá prechádzať;
  • znak + označuje štartovú pozíciu hráča.

Napíšte program v konzolovom režime, ktorý pomocou backtrackingu nájde v tomto labyrinte najdlhšiu cestu. Samozrejme, že hráč začína v štartovom políčku a na žiadne políčko nestúpi viackrát. Skončiť s cestou môže na hociktorom políčku. Program, keď nájde najlepšie riešenie, vypíše ho do textovej plochy, pričom políčka cez ktoré prejde vypíše ako znak '.'.

Riešenie zadefinujte v unite Unit1 do triedy TLabyrint tak, aby sa riešenie spustilo po spustení hlavného programu. Ako riešenie skúšky budete odovzdávať len tento jeden unit. V tomto unite nepoužívajte žiadne globálne premenné.

Použite tento projekt ako základ vášho riešenia.