Třetí série čtvrtého ročníku KSP
Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.Zadání úloh
4-3-1 Vyhledávání
Jsou zadány dva řetězce znaků A[1… N] a B[1… M], pro které platí N>M. Napište a dokažte algoritmus a program, který zjistí, zda je řetězec B obsažen uvnitř řetězce A. Snažte se, aby program pracoval co nejrychleji i pro velmi velká N, kdy je řetězec A uložen ve vnější paměti (např. na disku). Přitom můžete předpokládat, že řetězec B má rozumnou délku (tzn. vejde se do paměti).
4-3-2 Komprimace souboru
Existují různé způsoby, jak zakódovat soubory znaků, aby zabíraly co možná nejmenší prostor. My jsme pro vás připravili jeden způsob, který není nijak optimální, ale na kterém se budete moci něco naučit (alespoň doufáme). Vstupní soubor, obsahující znaky s kódem 0–255, zakódujete následujícím způsobem: Vstupní soubor rozdělíte od začátku do dvojic znaků, zjistíte četnost jednotlivých dvojic a podle toho je seřadíte. Prvních 255 dvojic bude kódováno jedním bytem (pořadové číslo), dalších 255 pomocí dvou bytů (0, pořadové číslo - 255), dalších 255 pomocí tří bytů (0, 0, pořadové číslo - 510), atd. Výstupní soubor bude začínat celkovým počtem různých dvojic na vstupu (kódují dva znaky), dále bude následovat jejich seznam ve výše určeném pořadí podle četnosti. Po této úvodní tabulce následuje zakódování vlastního vstupního souboru.
Napište dva programy, jeden na zakódování vstupního souboru, druhý na jeho rozkódování. Prémie: Navrhněte zlepšení při zachování základní myšlenky rozdělení do dvojic.
4-3-3 Dělení polynomů
Jsou dány dva textové řetězce, které jsou zápisem polynomu proměnné x. Přitom můžete předpokládat, že vstupní řetězce jsou syntakticky správně a polynomy odpovídající těmto řetězcům mají stupeň nejvýše K, kde K je daná konstanta. Vaším úkolem je pro textové řetězce P, Q určit odpovídající polynomy p, q a polynomy r, s, pro které platí:
Výstupem vašeho programu budou dvě pole r[0…K] a s[0…K], přičemž platí:
| r | = r[0] + r[1]·x + r[2]·x2 + … + r[K]·xK |
| s | = s[0] + s[1]·x + s[2]·x2 + … + s[K]·xK |
4-3-4 Minesweeper
Ti z vás, kteří již přišli do styku s MS Windows, jistě tuší, co je čeká. Pro ty ostatní nejprve pravidla hry Minesweeper: Je dán hrací plán N×M polí. Každé pole může obsahovat buď minu, nebo informaci o rozložení min na sousedních polích. Informace o minách na sousedních polích je číslo od 0 do 8, které udává počet sousedních polí obsahujících minu. Na začátku hry jsou všechna pole zakryta, tzn. hráč neví, co pole obsahuje. Úkolem hráče je odkrýt všechna pole neobsahující minu a pole s minou označit.
My po vás nebudeme chtít nic tak složitého. Vaším úkolem bude vyřešit načtení rozehrané partie (tj. která pole jsou odkryta a co odkrytá pole obsahují) a napsat proceduru, která pro načtenou partii určí jedno možné rozložení min vyhovující odkrytým informacím (tzn. nebudete odkrývat žádná další pole).