Z následující stránky si můžete stáhnout zdrojové kódy i spustitelné verze vzorových řešení úloh krajského kola. U některých úloh je i připojen popis řešení.
Vzorové řešení (C)
Vlastní výpočet běží v samostatném vlákně a probíhá na dvě kola. Výpočet v samostatném vlákně jsem zvolil pro hladší průběh a nastavil jsem mu nízkou prioritu procesu (IDLE). Grafické rozhraní tak reaguje okamžitě a pokud má PC více jader/procesorů úloha se rozdělí mezi jádra a výpočet má jádro samo pro sebe. Program vytváří v adresáři, odkud je spuštěn, pracovní soubor. Musí k tomu mít dostatečná práva a kapacitu disku (více viz dále).
První kolo výpočtu stanovuje tabulku prvočísel, druhé vybírá vhodné dvojice prvočísel a vypisuje je do souboru. Obě činnosti sice lze udělat v jednom kole, ale je to pomalejší a zdrojový text je méně přehledný.
První kolo - stanovení prvočísel - používá optimalizované Erathostenovo síto, info viz například: http://rcernobila.czweb.org/algoritmy/erat.htm nebo obecně Google. Optimalizace je provedena tak, že jsou vynechány násobky dvou, tří a pěti. Vyškrtávání násobků začíná od sedminásobku, protože všechny ostatní už jsou vyškrtnuty, jde se po lichých násobcích a konec je odmocnina(Limit).
Data jsou ukládána do bitového pole. Díky optimalizaci z každých 30ti po sobě jdoucích čísel zbyde 8 čísel, které jsou potenciální (možná) prvočísla. Ty jsou uložena do 8 bitů, tedy právě do jednoho bytu. Vychází nám tedy potřeba paměti na bitové pole takto: potreba_v_bytech = Limit / 30 Pokud jsme schopni vytvořit bitové pole velikosti 2GB, můžeme toreticky počítat s Limitem cca 60 miliard! Bude to ovšem trvat řádově dny výpočtu. Praktické maximum je Limit = 2 miliardy s dobou výpočtu několik minut. Bitové pole je ukládáno pomocí paměťově mapovaného souboru, což je způsob, jak pracovat s velkými soubory stejně rychle jako s pamětí. Vstupněvýstupní operace a mapování provádí jádro Windows a optimalizovaně. Z hlediska programátora se jedná o práci s pamětí a záleží jen na programovacím prostředí zda to podporuje. Technologické maximum možné dostupné paměti se liší podle druhu a nastavení Windows. Pro Windows Xp Professional v základním nastavení je to teoreticky 2GB. Běžně je to o 100-200MB méně. S velikostí operační paměti to nesouvisí!
Druhé kolo - výpis dvojic prvočísel do souboru je optimalizován tím, že potenciální dvojice prvočísel jsou vždy ve stejném bytu a navíc jsou bitově vedle sebe. Tak je možno je testovat jedním testem. Dvojice prvočísel z první třicítky se vypisuje explicitně, všechny ostatní se vypisují podle zjištěných dat.
Vzorové řešení (Basic)
Používají se dvě pole: puvodni a nove. Procedura JedenKrok spočítá podle zadaných pravidel z pole puvodni hodnotu pro pole nove. Po výpočtu hodnot všech buňek se nove zkopíruje do původní a zobrazí.
Pole je ze všech stran o jednu buňku delší, aby nebylo nutné testovat okraje.Vzorové řešení (Delphi)
Vzorové řešení (Visual C++)
Vzorové řešení (Java)
Vzorové řešení (Delphi)
Tezistem ulohy bylo po zadani kmenu jabloni nalezt zadany plot. Pote clovek musel jenom nacitat data a zobrazovat vystupy.
Pokud si jablone predstavime jako body v rovine, hledany plot je takzvany "konvexni obal", na jehoz nalezeni muzeme pouzit mnoho [ruzne dobrych] algoritmu. Pro zakladni prehled se muzete podivat na http://en.wikipedia.org/wiki/Convex_hull
Ve vzorovem reseni jsme pouzili tzv. Monotone Chain Convex Hull [je to asi nejjednodussi reseni], jehoz [ne moc pekny] popis lze najit bud http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull nebo http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm#Monotone Chain.
Zkracene jde asi o tohle: body si setridime podle x-ove souradnice a vezmeme nejlevejsi bod L a nejpravejsi bod P. Ty urcite v obalu byt musi. Pak zkonstruujeme zvlast horni a spodni cast obalu. Kazdou cast obalu pak budeme kontstruovat zleva. Budeme prochazet postupne body podle setridene x-ove souradnice. Kdyz zpracovavame dalsi bod, pridame ho na konec seznamu vrcholu, kteri tvori konvexni obal. Pak otestujeme, zda tri posledni body v tomto seznamu netvori "vkousnuti". Presneji, jsou-li posledni tri body a,b,c, zjistime, jestli uhel svirany poloprimkami ba a bc neni vetsi nez 180 stupnu [podle toho, v jakem smyslu merime uhly, dostaneme horni nebo spodni cast konvexniho obalu]. Kdyz tvori vkousnuti, bod b vyhodime a znovu otestujeme posledni tri body v seznamu obalu, ... Zastavime se kdyz posledni tri body vkousnuti netvori nebo jsou v obalu jenom dva body.
Takto jsme zpracovali jeden setrideny bod, vezmeme pak tedy dalsi, pridame na konec seznamu, opet vyhazujeme dokud musime, atd...
Nakonec ve dvou seznamech dostaneme horni a spodni cast obalu. Technicke detaily jako zjisteni, zda tri body tvori vkousnuti, muzete najit ve zdrojovych kodech.
Vzorové řešení (Visual C++)