Toto je více-méně konečný seznam, i když nevylučuji, že mě napadne ještě další úloha. Některé obtížnější úlohy z minulého semestru zůstali.
PRAVIDLA PRO ODEVZDÁNÍ:
Zápočtový program je opět možno zaslat e-mailem, ale součástí předání nakonec bude osobní vysvětlení programu, čímž student prokáže, že je skutečně jeho autorem. Nezbytnou součástí zápočtového program v letním semestru je i jeho písemná dokumentace. Ta by měla obsahovat: jméno a příjmení autora, datum poslední úpravy programu, zadání úlohy, popis vstupu a výstupu, popis a vysvětlení použité metody a vysvětlení hlavních datových struktur použitých v programu.
ÚLOHY:
1) Magické čtverce:(Vojtěch Sidorin) Magický čtverec řádu N je definován jako čtvercová tabulka s N řádky, která obsahuje čísla 1, 2, ..., N2 uspořádána tak, že součet čísel v každém řádku, sloupci i na hlavních diagonálách je stejný. Napište program, pro hledání magických čtverců. Vstupem do programu bude číslo N.
2) Magický šestiúhelník: Jiná varianta úlohy výše. V šestiúhelníkové síti (včelí plástev) lze vybrat šestiúhelník o straně N, který se skládá z H_N=3*N(N-1)+1 elementárních šestiúhelníčků. Například pro N=2 je velký šestiúhelník složen ze 7 elementárních (jeden je uprostřed a ostatní kolem). Magickým šestiúhelníkem nazveme takový šestiúhelník o straně N, v němž jsou vepsána čísla 1,2,...,H_N a to tak, že součet v každé přímce elementárních buněk sousedících navzájem přes stranu v šestiúhelníku je stejný (v šestiúhelníku jsou tři směry přímek podobně jako ve čtvercové síti dva: řádky a sloupce). Dá se ukázat, že existuje jediný magický šestiúhelník a to pro N=3. Napište program, který jej nalezne. Pozn: k výpisu lze s výhodou použít reprezentace šestiúhelníkové sítě pomocí znaků <>- .
3) Magické barevné čtverce: Mějme čtverec řádu N. Najděte obarvení čtverce N barvami takové, že na každém řádku i sloupci leží každá barva právě jednou a že na žádné diagonále neleží dvě stejné barvy.
4) Průchod obra lesem:(Jan Procházka) Les je definován jako čtverec o hraně H. Strom v lese je definován jako bod (=kmen) o souřadnicích X,Y uvnitř čtverce. Obr je definován jako kružnice o poloměru R. K levé a pravé straně lesa přiléhá skála. Zjistěte, zda se může obr projít lesem z jeho dolní hranice na horní hranici, aniž by vyvrátil strom, či musel otloukat skálu. Vstup: H, R, N a souřadnice stromů X1,Y1, ... , XN,YN. Výstup: Popis cesty (navrhněte vhodnou reprezentaci) nebo informace, že nelze projít.
5) Cykly na Rubikově kostce: Cyklem délky N na Rubikově kostce nazveme posloupnost N tahů, která končí v pozici v níž začala. Napište program pro nalezení všech cyklů délky nejvýše N. Poznámka: zaveďte si vhodné značení a vypisujte jen posloupnosti tahů, v nichž se nikde neprovede tah tam a zpět, tj. např. levá strana po směru hodinových ručiček a pak hned proti směru.
6) Mine sweeper: Naprogramujte hru mine sweeper (tu co bývá dodávána s operačním systémem Windows) - stačí v textovém režimu s pomocí unit CRT, kde pole jsou reprezentována vhodnými znaky a ovládání je pomocí klávesnice. Především správně udělejte automatické odkrývání prázdných polí. Dále přidělejte nápovědu: po stisknutí nějaké klávesy se barevně označí ta políčka na nichž jsou s jistotou bomby, nebo jsou s jistotou prázdná. Pokud taková políčka neexistují označí se políčka na nichž je nejmenší pravděpodobnost výskytu bomby a vypíše se jaká je to pravděpodobnost.
7) Křížovky: Napište program, který přečte ze souboru seznam slov a z nich vytváří křížovku NxN, tj. vepíše je tak, aby čtení po řádcích i sloupcích dávalo některé z daných slov. Možná rozšíření pokud si chcete hrát: 1) dovolit i mezery 2) načíst slovník tak, že si vezmete nějaký obsáhlý text (např. z www) a vyberete z něj seznam slov tak, aby se neopakovala.
8) Bludiště: Bludištěm budeme rozumět čtverec NxN na čtverečkovaném papíře v němž některé čtverečky jsou vyplněny (zdi). Přitom z každého políčka nepředstavujícího zeď se dá dojít do každého jiného takového políčka a zdi se nesmějí dotýkat vrcholem (jen hranou) a neexistují žádné políčko, které by sousedilo (přes hranu) jen se zdí nebo jen s volnými políčky. Napište program, který náhodně vygeneruje a vykreslí (stačí v textovém režimu) nějaké bludiště s těmito vlastnostmi. Uživatel zadá souřadnice dvou bodů bludiště a program vykreslí nejkratší cestu bludištěm mezi těmito body.
9) Minotaurus: Jako předchozí úloha, ale cesta se bude hledat metodou prohledávání do hloubky s průběžným vykreslováním pozice během hledání a tažením klubka niti za sebou (když jdu dál klubko odmotávám, když se vracím namotávám tj. zkracuji niť).
10) Piškvorky: Napište program pro hraní piškvorek. Možnosti: 1) hraje uživatel s počítačem 2) domluví se vás více a napíšete program společně, ale každý zvlášť vytvoří proceduru pro nalezení co nejlepšího dalšího tahu - program potom sám provede turnaj mezi procedurami a vypíše statistiku výsledků.
11) Jízdní řády: Napište program, který načte soubor jízdních řádů a nalezne nejrychlejší spojení ze zadané stanice A do zadané stanice B. Vstup: ze souboru jízdní řády v následujícím tvaru, a dále z klávesnice název počáteční a cílové stanice a nejpozdější čas příjezdu do cíle.
12) Kalkulátor pro polynomy: Polynom je reprezentován pomocí lineárního spojového seznamu tak, že v každém prvku seznamu jsou uloženy hodnoty koeficientu a exponentu jednoho členu polynomu. Prvky seznamu jsou uspořádány sestupně podle hodnot exponentu. Členy s nulovým koeficientem se do seznamu neukládají. Napište program, který přečte ze souboru sloupec polynomů s celočíselnými koeficienty a provede s nimi zadané operace. Definice operací jsou od definic polynomů odděleny řádkem začínajícím znakem # a podobně jsou ukončeny definice operací. V definicích operací se na polynomy odkazuje symboly p1,p2,...,pn, kde n je počet vstupních polynomů. Operace jsou složeny z elementárních operací + - * a závorek. Při vyhodnocování výrazů respektujte priority operací a závorky. Vzor vstupního souboru. Vzor výstupu.
13) Master Mind: Navrhněte algoritmus a napište program pro hru Master Mind (česky nazývaná někdy Logik). Základní varianta: Zadejte barvy kolíčků z klávesnice a nechte program vypsat vzorovou partii. Možné rozšíření: na začátku volba zda chcete zadávat barvy nebo hádat čísla, která vygeneruje náhodně počítač.