Vstupem je matice 9 x 9 uložena v textovém souboru, z části zaplněna čísly. Prázdná pole jsou reprezentavána 0. Implementujte vhodný algoritmus (např. backtracking) k nalezení kompletního řešení zadané úlohy. Program výsledek vypíše na obrazovku nebo do souboru.
Vstupem je matice 8 x 8 uložena v textovém souboru, která reprezentuje stav šachové partie s malým počtem figurek. Program řeší úlohu, zda hráč může vyhrát do n tahů pro malé n zadané uživatelem (maxiálně 4-5). Program poradí hráči následující tah (nebo posloupnost tahů hráče).
Vytvořte program, který bude schopen ze zápisu římského čísla (např. MCDXXIII) odvodit arabský zápis (v našem případě 1423). Pokud bude zápis neplatný (podle pravidel pro zápis římských čísel), program by to měl poznat (písmena musí být ve správném pořadí, mohou se vyskytovat maximálně 3 stejné znaky za sebou atd.). Opačnou úlohu, tj. převod arabského zápisu na římský, implementujte také. Program by měl generovat římská čísla samozřejmě také podle pravidel. Vstup se v cyklu zadává z klávesnice, program okamžitě napíše správný výsledek, případně oznámí, že je vstup neplatný. Program by měl rovněž umět načíst více hodnot ze souboru zadaného uživatelem a vypsat pro ně výsledek (do souboru zadaného uživatelem).
Implementujte datovou strukturu pro uložení řídké čtvercové matice NxN tj. takové, která má na každém řádku jen pár nenulových prvků. Matici uložte pomocí formátu COO. Implementujte následujicí funkce: vložení prvku, násobení matice a vektoru, násobení skalární hodnotou, násobení dvou matic, součet dvou matic, načtení libovolného prvku matice, načtení matice ze souboru a její výpis do souboru.
Implementujte datovou strukturu pro uložení řídké čtvercové matice NxN tj. takové, která má na každém řádku jen pár nenulových prvků. Matici uložte pomocí formátu CSR. Implementujte následujicí funkce: vložení prvku, násobení matice a vektoru, násobení skalární hodnotou, násobení dvou matic, součet dvou matic, načtení libovolného prvku matice, načtení matice ze souboru a její výpis do souboru.
Implementujte algoritmus pro lexikografické třídění textového dokumentu v českém jazyce (podle pravidel pro abecední řazení v češtině). Ukažte funkčnost algoritmu na vhodné aplikaci (např. setřídění řádek v textovém souboru). Program by měl načítat zadání a vypisovat výsledeky z/do souboru. Alternativně pro jiný národní jazyk (po domluvě).
Implementujte vhodnou datovou strukturu pro reprezentaci neorientovaného grafu s ohodnocenými hranami a implementujte alespoň dva odlišné algoritmy pro hledání minimální kostry (např. hladový, Primův, Borůvkův ap.). Příklady algoritmů najdete např. zde. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru.
Implementujste alespoň dva různé algoritmy založené na prohledávání grafu do hloubky nebo do šířky. Například to mohou být úlohy nalezení topologického uspořádání uzlů grafu, nalezení komponent souvislosti nebo silných komponent, zjišťování acykličnosti, hledání nejkratší cesty v grafu apod. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru. Je třeba předběžná specifikace konkrétního zadání.
Zvolte si jiný zajímavý grafový algoritmus/algoritmy (podle náročnosti, např. problém nalezení maximálního toku v síti). Navrhněte vhodnou datovou strukturu pro reprezentaci grafu a implementujte nad ní tento algoritmus. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru. Je třeba předběžná specifikace konkrétního zadání.
Známá hra Logik. Hra je parametrizována dvěma čísly: počet pozic N (typicky 4) a počet barev M (typicky 6). První hráč na počátku zvolí nějakou N-prvkovou kombinaci daných barev (mohou se i opakovat), druhý se ji snaží uhodnout. V každém tahu druhý hráč navrhne nějakou kombinaci barev a první mu na ni odpoví dvěma čísly: počet správně uhodnutých pozic a počet barev, které sice v utajované kombinaci jsou, ale na jiném místě (tedy například je-li tajná kombinace 1232 a druhý hráč hádá 1423, je odpověď "1,2"). Zadání úlohy specifikuje uživatel. Můžete zkusit implementovat algoritmus, který kombinaci barev efektivně hádá – začněte například s množinou všech 6^4 kombinací, z které postupně nepřípustné kombinace vyřazujete. Program v každém kroku hádá takovou kombinaci, která mu nejvíce napoví (průměrně tedy bude moci nejvíce nepřípustných kombinací škrtnout). Od programu se očekává, že pro typické zadání úlohy pro N=4 a M=6 bude schopen do osmi tahů a v reálném čase problém vyřešit.
Známá hra, ale lehce modifikovaná. Pole NxM. Po odkrytí stanoveného počtu polí počítač na odkrytém poli zobrazí minu právě tehdy, když z dosud zveřejněných informací nelze odvodit, že na této pozici mina být nemůže. Stačí textová verze, výpis stavu hry na obrazovku. Alternativně můžete naprogramovat tzv. hodný minesweeper (pokud pro žádné políčko nelze odvodit, že na něm mina být nemůže, tak ji na právě odkrytém políčku nezobrazí).
Naprogramujte textovou kalkulačku. Uživatel zadá na vstup aritmetický výraz sestávající z operandů (obecně desetinných čísel a proměnných), závorek a operátorů z předem známé množiny. Výraz se vyhodnotí s ohledem na priority operátorů a závorky. Implementujte možnost zavádění uživatelských proměnných a následné počítání s nimi. Nezapomeňte, že číslo je obecně reprezentováno více znaky, stejně jako název proměnné – je tedy nutné nejdřív výraz rozdělit na jednotlivé elementy. Samozřejmostí je, že si program umí poradit nejen s binárními operátory (levě i pravě asociativními), ale také s unárními, jako je například faktoriál či unární minus.
Spočítejte hodnotu iracionálního čísla pí na n desetinných míst (n zadá uživatel, např. 1000). Pro výpočet využijte například toho, co víte o Taylorových řadách (postupů existuje více, můžete zvolit i jiný). V rámci řešení úlohy navrhněte vhodnou datovou strukturu pro počítání s dlouhými čísli (například spojový seznam) a implementujte nad ní potřebné aritmetické operace.
Spočítejte hodnotu Eulerovy konstanty na n desetinných míst (n zadá uživatel, např. 1000). Postupů existuje více (např. pomocí vyjádření e pomocí součtu řady). V rámci řešení úlohy navrhněte vhodnou datovou strukturu pro počítání s dlouhými čísli (například spojový seznam) a implementujte nad ní potřebné aritmetické operace.
Implementujte knihovnu pro B-strom obsahující základní operace nad touto datovou strukturou (vkládání a mazání prvků, vyhledávání, načtení hodnot ze souboru, vizualizace apod.). Funkčnost knihovny demonstrujte na nějaké zajímavé aplikaci. Je třeba předběžná specifikace konkrétního zadání.
Implementujte knihovnu pro AVL-strom obsahující základní operace nad touto datovou strukturou (vkládání a mazání prvků, vyhledávání, načtení hodnot ze souboru, vizualizace apod.). Funkčnost knihovny demonstrujte na nějaké zajímavé aplikaci. Je třeba předběžná specifikace konkrétního zadání.
Nějaká zajímavá aplikace metody Monte Carlo (např. pro výpočet obsahu obrazce nebo Millerův–Rabinův test prvočíselnosti). Je třeba předběžná specifikace konkrétního zadání.
Nějaká zajímavá aplikace prioritní fronty. Prioritní frontu implementujte pomocí vhodné datové struktury (např. AVL strom). Je třeba předběžná specifikace konkrétního zadání.
Kochova vločka je jeden ze známých fraktálů. Může být zkonstruován tak, že začneme od rovnostranného trojúhelníku a postupně dělíme všechny úsečky v obrázku na třetiny, přičemž prostřední část vždy vyjmeme a nahradíme dvěma stejně dlouhými částmi tvořícími "osten". Implementujte rekurzivní algoritmus typu rozděl a panuj, který spočítá souřadnice jednotlivých bodů Kochovy vločky daného řádu (řád zadá uživatel, např. 5). Výsledkem bude 1) soubor se dvěma sloupci dat (x-ové a y-ové souřadnice bodů), 2) soubor ve formátu SVG (nebo jiném vhodném formátu pro snadné zobrazení obrázku).
Uživatel zadá na vstup polynom v základním tvaru (např. x^5 - 2 x^4 - 10 x^3 + 20 x^2 + 9 x - 18). Program vrátí polynom rozložený na součin celočíselných kořenových činitelů pomocí Hornerova schématu (např. (x-1)(x+1)(x-2)(x-3)(x+3)). Program by měl zvládnout i opačnou úlohu (roznásobení závorek a převod na základní tvar). Vstup se v cyklu zadává z klávesnice, program okamžitě napíše správný výsledek, případně oznámí, že je vstup neplatný. Program by měl rovněž umět načíst více zadání ze souboru zadaného uživatelem a vypsat pro ně výsledek (do souboru zadaného uživatelem).
Řešení klasické dětské skládačky Patnáctka. Uživatel zadá na vstup zadání úlohy (alternativně program zadání načte ze souboru). Program vypíše postup řešení, např. ve tvaru 15L 5N 7D 4P (L,P,N,D značí směr pohybu dané kostičky), na požádání vypíše do souboru i průběžné rámečky.
Implementujte některý z algoritmů pro vnější třídění (např. přímé slučování).
Uživatel zadá na vstup soustavu algebrogramů.
Příklad:
A * B = CA
A * C = D
D * A = EC
Program vypíše řešení algebrogramu (měl by umět postupně nalézt všechna řešení).
Implementujte operace +,-,*, celočíselné dělení (div, mod), konstanty, proměnný počet řádků/sloupců, různá písmena reprezentují různé cifry vždy/nikoliv nutně (obě varianty).
Naprogramujte textovou kalkulačku pro polynomy. Uživatel zadá na vstup výrazy ve tvaru (1 + x^2)*(x + 1) nebo (0.3 - x^2)^5. Program vrátí polynom v základním tvaru (např. x^3 + 2*x + 1). Implementujte operace sčítání, odečítání, násobení, "chytré umocňování".
Uživatel zadá na vstup zvolený počet nějaké číslice, např 4444 nebo 333 a hodnotu přirozeného čísla N. 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í (+,-,*,/). Nápověda: zkuste použít dynamické programování. Program vypíše řešení pro zadané N.