První 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-1-1 Sedlový bod

Sedlovým bodem matice A o rozměrech M×N je její prvek ai,j právě tehdy, když platí pro všechna k, l (0<k≤ M, 0<l≤ N) ak,j ≤ ai,j ≤ ai,l nebo ak,j ≥ ai,j ≥ ai,l. Napište a dokažte algoritmus a program, který k zadané matici A:array[1..M,1..N] of integer zjistí, zda v ní existuje sedlový bod, a vypíše souřadnice alespoň jednoho sedlového bodu matice A.

4-1-2 Master Mind

Master Mind je hra pro 2 hráče. Jednoho budeme nazývat „hadač“, druhého „byrokrat“. Na začátku hry byrokrat zvolí variaci 4 čísel ze 6 možných (1, 2, 3, 4, 5, 6). Přitom se:

  1. čísla mohou opakovat
  2. čísla nemohou opakovat.
Ve variaci záleží na pořadí! Tuto volbu byrokrat provede (jak je zvykem) tak, aby ji hadač neznal. Úkolem hadače je tuto variaci určit na co nejmenší počet pokusů. Každý pokus hadače byrokrat ohodnotí dvěma čísly. První určuje počet správně určených čísel na správné pozici ve variaci, druhé počet správně určených čísel na nesprávné pozici ve variaci. Napište program (vlastně dva programy – úlohy a, b), který si s vámi zahraje Master Mind v úloze hadače. Hodnotí se efektivnost algoritmu daná maximálním počtem pokusů potřebných k určení variace.

Příklad hry – variace je 1 2 3 1:

Hadač: 1 1 2 2 Byrokrat na to: 1 2
Hadač: 1 2 1 3 Byrokrat na to: 2 2
Hadač: 1 2 3 1 Byrokrat na to: 4 0

4-1-3 Dělení čtverce

V kartézské soustavě souřadnic je pevně zadán čtverec s vrcholy (0,0), (100,0), (100,100) a (0,100). Dále je v tomto čtverci zadáno N bodů. Napište a dokažte algoritmus a program, který tento čtverec rozdělí lomenými čarami na N částí (v každé části bude právě jeden zadaný bod, který nazveme vedoucím části) tak, aby pro všechny body jedné části platilo, že jejich vzdálenost od vedoucího bodu této části je menší než vzdálenost od vedoucích bodů ostatních částí. Výstupem programu bude posloupnost souřadnic počátečních a koncových bodů jednotlivých úseček.

4-1-4 DownLoad

Představte si, že máte tiskárnu, na které lze tisknout pouze znaky, jejichž tvar je uložený v paměti tiskárny. Kapacita paměti vystačí pouze pro N znaků (N≤ 256). Napište a dokažte algoritmus a program, který vytiskne text zadaný v rozšířeném ASCII kódu (tj. znaky 0… 255) na této tiskárně. Přitom vždy při tisku znaku Z1, který není uložen v paměti, je třeba zavolat proceduru DownLoad(Z1,Z2), která vypustí z paměti tiskárny znak Z2 a místo něj vloží znak Z1. Tato operace je časově dosti náročná, a proto hlavním kritériem při hodnocení vašeho programu bude počet volání procedury DownLoad. Při psaní programu předpokládejte, že po spuštění jsou v paměti tiskárny samé mezery (ASCII kód 20h).