Druhá série páté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

5-2-1 Milijón čísel

Na disku je soubor s nejvýše 27 000 16-bitovými čísly od 1 do 27 000. K dispozici je dost místa na disku, ale pouze 4 KB (= 4 096 bajtů) paměti. Vaším úkolem je napsat program, který zkontroluje, zda se v souboru nějaké číslo opakuje, a pokud ne, vytiskne všechna čísla v rostoucím pořadí.

Poznámka: Tato úloha prý vznikla v USA při rozdělování volebních okrsků do volebních okruhů.

5-2-2 Posloupnost

Na vstupu je dána uspořádaná posloupnost celých čísel a1, … , an. Navrhněte algoritmus a napište program, který zjistí, zda se ve vstupní posloupnosti vyskytují tři čísla x, x2, x3 a pokud ano, vytiskne je.

Příklad: Vstupní posloupnost je -5, -1, 2, 4, 5, 7, 8, 10; hledaná čísla jsou 2, 4, 8.

5-2-3 Generování

Vstupem programu jsou reálná čísla p1, … , pn, pro než platí:

0 ≤ p1 ≤ p2 ≤ … ≤ pn ≤ 1
p1 + p2 + … + pn = 1

V určitém místě programu bude třeba generovat náhodná čísla od 1 do n, a to tak, aby číslo i bylo generováno s pravděpodobností pi. Napište co nejrychlejší funkci, která bude taková čísla generovat.

Nápověda: Před vlastním generováním náhodných čísel bude jistě dost času na nějakou vhodnou předvýpočetní přípravnou proceduru.

5-2-4 Jsem to já?

Napište program, který, najde-li na vstupu svůj vlastní zdrojový text, vytiskne „To sou teda fóry“, v opačném případě vytiskne svůj zdrojový text.

5-2-5 Konečně

Sestrojte konečné automaty, které rozpoznávají následující jazyky:

L1={w∈{a,b}*; w=xbaba, x∈{a,b}*}
L2={w∈{1,2,3,4,5}*; w  je ostře rostoucí posloupnost}

Příklad: Do jazyka L2 patří například 135, 12, e. Nepatří do něj například 534, 12321.

Poznámka: Sestrojením konečného automatu rozumíme vypsání složek pětice a nakreslení obrázku. Krátký studijní text o konečných automatech najdete v kapitole 11.