Meno: Michal Korbela
Škola: Gybmnázium J.J. Bánovce nad B. Radlinského 665/2, 95701
Adresa domov: Brezolupy 160, 95701
Trieda: kvinta
Úloha č.5 - Popis



Program si zapíše len počet domín rovnakého druhu - čo vedie ku konštantnej pamäťovej zložitosti o(1).
Bude si ich zapisovať do tabuľky kde riadok a stĺpec určujú čísla na domine + 1 aby sme predišli šahaniu mimo poľa a vrí výpise čohokoľvek zas všetko znížime o 1. Tabuľka bude mať rozmery 7*7 polí.
 Aby sa nám čísla neopakovali využijeme len polovicu tabuľky a to tak že budeme dominá zapisovať tak:
Ak na domine budú 2 rovnaké čísla - toto domino si nazveme špeciálne a budú sa zapisovať do tabuľky so súradnicami a,a kde a sú čísla na domine.
Ak budú na domine 2 rôzne čísla tak si vyberieme jedno z nich a označíme ho a a druhé b. Zapíšeme ho do okienka takého, ak je a<b, tak a určuje stĺpec a b riadok a ak je b<a tak a určuje riadoka b stĺpec.
Do tabuľky značíme len počty domín. Tabuľka sa nachádza v poli "pole".
informácie o číslach si značíme v poli "cisla" a značíme si len počet jednotlivých čísel na dominách - pozor nie špeciálnych.


Prvé čo začneme testovať sú počty nepárnych čísel. Tie dostaneme zvyškovým delením počtov čísel(informácie v poli cisla). Nepárnych čísel môže byť len 0 alebo 2. Ak bude nepárnych čísel 0 znamená to, že rad nemá koniec môžme začať ukladať od hociktorého domina a vždy to bude možné poukladať ak vždy keď to bude možné tak vyložíme aj všetky špeciálne dominá.
Ak bude počet nepárnych čísel 2 znamená to, že rad má začiatok a koniec - dá sa poukladať, ale len vtedy , keď ho budeme ukladať podľa nasledujúcich pravidiel: vyložíme všetky špeciálne dominá ktoré majú na sebe čísla, ktorých je nepárny počet(vyberieme si z nich jedno a označíme ho a, druhé bude b). Potom vyložíme domino ktoré obsahuje číslo a. Potom si označíme jedno domino ktoré odsahuje číslo b( pozor nie špeciálne) tak aby sme ho nevyhodili skôr ako má byť - čiže na koniec. Potom môžme začať ukladať dominá v ako chceme a zase s tým, že ak bude možné vyhodiť špeciálne dominá, tak ich vyložíme.
Ak už nebudeme mať čo vyhodiť, vyhodíme posledné domino a vypíšeme všetky špeciálne dominá( ak ešte zostali).

Ale pred tým ako ich začneme vypisovať, musíme zistiť, či sa dajú poukladať( to neznamená, že keď rad má začiatok a koniec že sa dá poukladať môžu to byť n kruhov - 0 koncov, alebo n kruhov a 1 rad.....)

To začneme testovať tak, že si zvolíme jedno domino. Ak má byť toto domino v rade, tak sa vieme pomocou tohto domina dostať k hociktorému dominu.
Testovanie spočíva v tom, že budeme hľadať také dominá, ktoré obsahujú jedno číslo z domina. Ak nejaké nájdeme(može ich byť 5 - jedno už máme) tak začneme testovať tie, až pokým budú všetky dominá otestované.
Potom skontrolujeme, či všetky dominá boli prezreté, ak áno, tak sme vyhrali, a môžeme ísť vypisovať, ak nie tak máme smolu vypíšeme Nedá sa.


Vypisovanie:
Ak rad nemá začiatok a koniec - nájdeme si nejaké domino, vypíšeme ho a budeme hľadať ďaľšie také ktoré obsahuje posledné číslo na domine. Vždy keď to bude možné vypíšeme špeciálne dominá ( je dobré sa ich zbaviť, lebo sa ich už možno nebude dať zbaviť.)
Ak existuje taká situácuia že existujú, len špeciálne dominá neprebehne ani náš cyklus výpisu, ale hneď sa vypíšu.



Ak má rad začiatoka a koniec, tak ako prvé vypíšeme špeciálne dominá toho čísla ktoré má byť na začiatku ( číslo a), potom vypíšeme domino, ktoré obsahuje číslo a.Potom si označíme koniec  - domino ktoré má byť na konci -  a to urobíme tak že vymažeme jedno domino ktoré má byť na konci a začneme vypisovať dominá. Ak už nenájdeme také domino ktoré potrebujeme vypíšeme posledné domino, a to tak, že vieme že to domino musí začínať na číslo ktoré je na konci radu. Čiže vypíšeme znova číslo ktoré má byť na konci radu a za ním číslo b. A určite je to domino ktoré sme vymazali. Potom vypíšeme už len špeciálne dominá( ak existujú).


Čo sa týka pamäťovej zložitosti - ako som už spomínal je konštantná - nezávisí od počtu domín.
Časová zložitosť - tá je lineárna - záleží od počtu domín O(pocet) - kde pocet je počet domín.