Zadání zápočtových programů, zimní semestr

1. Prvočísla
   Napište program, který graficky znázorní rozmístění prvočísel v intervalu ( 1 ; N ). Pokuste se o co největší N. Výsledek umožněte uživateli vytisknout (nemusí to tisknout přímo váš program).
2. Dlouhá čísla + –
   Vytvořte program pro sčítání a odčítání dlouhých čísel. Výraz může mít více operandů než jen dva.
3. Polynomy
   Napište podprogramy na binární operace (+ - *) s polynomy. Jejich funkčnost demonstrujte v jednoduchém programu.
4. Soustava lineárních rovnic
   Program řeší soustavu lineárních rovnic. Rovnice jsou zadané polynomem v textovém tvaru. Předpokládejte, že se jedná o navzájem nezávislé rovnice a soustava má právě jedno řešení.
5. Dělení dlouhých čísel
   Vytvořte program pro dělení (celočíselné se zbytkem) dvou dlouhých čísel.
6. Matice
Implementace běžných operací s maticemi (sčítání, násobení, inverze, determinant, ...).
7. Symbolické derivace I
   Napište program, který zjednoduší a zderivuje polynom (bez funkcí)
8. Složenky
   Napište program, který vypíše slovy číslo, které mu uživatel zadá.
9. Zápis zlomku
   Sekvenční zápis zlomku převeďte do přehledného tvaru s různě dlouhými zlomkovými čarami.
10. Formátování zdrojového textu programu v pascalu.
    Napište program, který upraví odsazení řádků v pascalském zdrojáku, tak aby bylo snadné rozpoznávat jednotlivé bloky. Pokud si to uživatel přeje, tak také očísluje jednotlivé úrovně vnoření. Vstupem i výstupem je textový soubor se syntakticky správným zdrojovým kódem v pascalu.
11. Kontrola závorek
    Napište program, který zkontroluje uzávorkování ve výrazu. Výraz používá několik různých typů závorek. Některé závorky mohou být i více znakove. Všechny otevřené závorky musí být zase uzavřeny a žádné se nesmí křížit. Seznam závorek si program načte z textového souboru.
12. Morseovka
    Napište program, který převede daný text do morseovky a dokáže také obráceně zápis v morseovce. Program umí i dekódovat. Kód jednotlivých znaků si program načte ze vstupního souboru.
13. Mřížková šifra
    Program, zašifruje text podle zadané mřížky. Šifrovaný text i mřížka jsou zadány v samostatných souborech. Program umí i dekódovat.
14. Logik (Mastermind)
    Program hraje hru Mastermind (barvy se mohou opakovat) s uživatelem. Počítač generuje náhodné zadání a provádí ohodnocení tahu uživatele. Hra je parametrizována dvěma čísly: počet pozic N (typicky 5) a počet barev M (typicky 8). Barvy lze nahradit čísly.
15. Šibenice (Hangman)
Hráč hádá text (například přísloví, názvy filmů, ..., za pomoci slovníku), jehož rozdělení znaků do slov je předem známo. V každém tahu navrhne jedno písmeno a počítač mu odpoví, kde všude se v hádaném slově vyskytuje. Čím méněkrát se splete tím lépe. Varianta pro dva hráče - v hádání písmen se střídají, tak že hráč se dostane na tah po chybě protihráče.
16. Matfyzácké pexeso
Pexeso, v němž když hráč otočí dvě různé kartičky, vrací je zpět v opačném pořadí. Program simuluje prostředí hry pro N hráčů s M dvojicemi karet. Obrázky lze nahradit vhodnými znaky, texty, čísly, výrazy ...
17. Miny (MineSweeper)
    Naprogramujte hru a navrhněte vhodně komunikaci s uživatelem v textovém režimu. Program zobrazuje průběžný stav hry, Hra končí po označení všech min, nikoliv nutně po odkrytí všech volných polí
18. Lodě
    Navrhněte vhodné prostředí pro hru Lodě. Hru budou hrát dva hráči proti sobě na dvou různých instancích programu (na různých počítačích). Programy spolu nemusí nutně komunikovat. Program umožní zadat (načíst ze souboru) rozmístění lodí, zkontroluje ho a poté slouží k zaznamenávání a zobrazení průběhu partie. Program rozpozná konec hry a označí vítěze.
19. Piškvorky
    Naprogramujte hru dvou uživatelů. Navrhněte vhodně zobrazení a komunikaci s uživateli (v textovém režimu). Pozor, program musí rozpoznat, kdy hra končí a označit vítěze.
20. Reverzy
    Hraje se na mřížce 8 x 8, na počátku jsou uprostřed hracího plánu položeny dva černé (sousedí pouze rohem, na [4;4] a [5;5]) a dva bílé ([5;4] a [4;5]) kameny. Hráči se střídají v pokládání kamenů své barvy, při položení kamene na dané políčko se všechny nově vzniknuvší kombinace (v řádku, sloupci či úhlopříčce) dvou kamenů právě táhnoucího hráče, mezi nimiž jsou (bez prázdných políček) kameny druhého hráče, přebarví na barvu táhnoucího hráče. Položení kamene, po kterém by nenásledovalo žádné přebarvení, není dovoleno. Hra končí, nemůže-li hráč, který je zrovna na tahu, nikam položit další kámen. Vyhrává ten, komu patřilo na konci hry více kamenů.Naprogramujte hru dvou uživatelů. Navrhněte vhodně zobrazení a komunikaci s uživateli v textovém režimu. Pozor, program musí rozpoznat, kdy hra končí a označit vítěze.
21. Dáma
    Naprogramujte hru dvou uživatelů. Navrhněte vhodně zobrazení a komunikaci s uživateli v textovém režimu. Úkolem programu je také hlídat dodržování pravidel (povinné skákání). Pozor, program musí rozpoznat, kdy hra končí a označit vítěze.
22. Logická hra LightsOut
    Je dána mřížka 5x5 a každé políčko představuje žárovku. Žárovka je zhasnutá nebo rozsvícená. Uživatel označí žárovku a tím překlopí její stav a zároveň všech jejich sousedek (nejvýše čtyř) přílehajících jednou stranou. Napište program, který pro daný počáteční stav navrhne řešení, jak zhasnout všechny žárovky. Algoritmus nemusíte vymýšlet, stačí imlementovat například algoritmus popsaný na Wikipedii. Správnost výsledku si můžete otestovat na těchto stránkách
23. Korespondenční šachy
    Program umožní dvěma hráčům hrát korespondenčně šachy. Program ze souboru načte situaci na šachovnici, umožní vhodně hráči zadat tah, zkontroluje, zda se jedná o korektní tah a situaci uloží do souboru, který je možno poslat druhému hráči. Počáteční situaci není třeba číst ze souboru, ale program si ji umí vygenerovat sám. Soubor se stavem na šachovnici by měl být textový nebo jiným vhodným způsobem umožněte zadat libovolnou situaci na šachovnici.
24. Atomy (Exploding Atoms)
Naprogramujte prostředí pro hru dvou hráčů. Hra se hraje na normální šachovnici. Na každém políčku je jedno atomové jádro, které může patřit jednomu z hráčů a mohou kolem něj obíhat elektrony. Na počátku hry nepatří žádné jádro nikomu a nikde nejsou žádné elektrony. Hráči se střídají, v každém tahu jeden z nich přidá elektron k některému ze svých atomů, případně k atomu dosud neobsazenému (který si tím přivlastní). Pokud tak počet elektronů dosáhne kritického množství (to je rovno počtu sousedů daného atomu, tedy 2 pro rohové atomy až 4 pro vnitřní), atom exploduje a jeho elektrony se rozletí do všech směrů k sousedním atomům, které tak rovněž připadnou táhnuvšímu hráči a případně také explodují atd. Hra končí, přijde-li jeden z hráčů o všechny své atomy (tím prohraje).
25. Sudoku
    Řešte sudoku o dané velikosti. Neřešte pouze hrubou silou, ale navrhněte nějaké vhodné zrychlení.
26. Life
    Simulace života buněk. Je dán čtvercový životní prostor N x N a v něm jsou buňky, které se vyvíjí v závislosti na svém okolí (např. buňka přežije do další generace, pokud má alespoň dva sousedy a naopak na prázdném políčku může vzniknout buňka, má-li právě dva živé sousedy). Ve vstupním souboru je počáteční rozložení buněk. Program pak simuluje generaci po generaci vývoj v celém prostoru.
27. Skoky po šachovnici
    Programu dáte definici šachové figurky (to jest nějak popíšete, jak se daná figurka může pohybovat, nemusí odpovídat skutečné hře šachy), velikost šachovnice a souřadnice počátečního políčka a on vymyslí, zda a jak je možno touto figurkou "obskákat" celou šachovnici (to jest navštívit každé políčko právě jednou) a skončit přesně tam, kde jsme začali.
28. Tvary
    Program, který pro dané N, vygeneruje všechny tvary skládající se z N čtverečků. Tvary musí být souvislé (čtverečky sousedí alespoň jednou hranou, vrchol nestačí) a nesmí mít díry (prázdný prostor obklopený čtverečky ze všech stran). Výsledek je možné uložit ve vhodně navrženém srozumitelném formátu do textového souboru. Úlohu můžete rozšířit o podmínku, že otočené tvary se považují za totožné.
29. Skládačka
    Úloha částečně navazuje na úlohu Tvary. Vhodně si navrhněte vstupní soubor popisující tvary. Tvary nemusí mít stejnou velikost. Program pro daný vstupní soubor a čísla N a M zjistí, zda je možné bezezbytku pokrýt tvary matici N x M. Výsledek vhodně zobrazte. Tvary je možné libovolně otáčet, nikoliv však převracet.
30. Hádankářský slovník
    Program, který si načte slovník (co řádka, to slovo) a pak odpovídá (rozumně rychle) na dotazy chtivých hádankářů. Hádankář zadá písmena a program vypíše všechna slova ze slovníku, která lze z písmen poskládat. Takový program by vám mohl být pomocníkem například při hře scrable.
31. Čtyři čtyřky
Napište program, který pro všechna přirozená čisla od 0 do N zjistí, jak je zapsat za pomoci čtyř čtyřek (respektive jiného počtu jiných číslic dle zadání uživatele) a běžných aritmetických operací.
32. Markovovské texty
Generování náhodného textu napodobujícího text zadaný (řekněme se stejnými pravděpodobnostmi výskytu znaku v závislosti na předchozích k znacích). Případně totéž pro délku slova.
33. Rychlé vyhledávání
Na vstupu je seznam slov (až stovky) a velice dlouhý text. Program spočítá výskyty každého ze slov seznamu v dlouhém textu. Předpokládejte, že ve vstupní text je tak velký, že si ho nemůžete nikam uložit a ani se v něm nemůžete vracet (například proto, že to je výstup nějakého jiného programu).
34. Rychlé nahrazování
Na vstupu je seznam až stovek dvojic slov a dlouhý text. Program v textu nahradí všechna první slova dvojic druhými z téže dvojice. Opět se nelze ve vstupním souboru vracet.