Jsou dána dvě kladná celá čísla N, K a posloupnost N celých čísel. Napište program, který určí délku maximálního K-hladkého úseku v dané posloupnosti čísel. Počet čísel N není předem shora omezen a může být velmi vysoký, naproti tomu hodnota K je rovna nejvýše 10. Při návrhu programu se zaměřte na dosažení co největší rychlosti výpočtu.
Příklad: Pro N=10, K=2 a posloupnost čísel 2 1 2 3 3 4 3 4 6 4 bude výsledkem číslo 6, neboť nejdelší 2-hladký úsek 2 3 3 4 3 4 je tvořen šesti čísly (další 2-hladké úseky, např. 2 1 2 3 3 nebo 4 6 4, jsou kratší).
P-II-2
V zemi je N měst označených čísly od 1 do N. Mezi městy
je vybudována silniční síť. Každá silnice spojuje vždy
dvojici měst. Všechny silnice jsou obousměrné. Mezi
některými dvojicemi měst přímá silnice nevede, ale z každého
města je možné dojet po silnicích do libovolného jiného
města (třeba i více různými způsoby). Všechna případná
křížení silnic mimo města jsou mimoúrovňová (pomocí mostů)
a neumožňují vozidlům přejet z jedné silnice na druhou.
Napište program, který určí, zda je možné rozdělit města do dvou skupin tak, aby každá dvojice měst patřících do stejné skupiny byla spojena přímou silnicí (tzn. uvnitř každé skupiny vede přímá silnice mezi každými dvěma městy). Nezáleží přitom na velikosti jednotlivých skupin (jedna ze skupin může být případně i prázdná), ale každé město musí být do některé skupiny zařazeno.
Vstupem programu je počet měst N a dále seznam všech silnic vedoucích mezi městy. Každá silnice je zadána dvojicí čísel měst, mezi nimiž vede.
P-II-3
Na hromádce je připraven předem známý počet N zápalek.
Dva hráči hrají hru, při které z hromádky střídavě odebírají
zápalky. Hráč, který je na řadě, musí v jednom tahu odebrat
takový počet zápalek, který je celočíselnou mocninou dvou
(tzn. lze ho vyjádřit ve tvaru 2Kpro vhodné celé nezáporné
číslo K). Vyhrává ten hráč, který vezme z hromádky poslední
zápalku.
Řídicí jednotka má konečnou paměť; říkáme, že se může nacházet v jednom z konečně mnoha stavů. Programem stroje je sada přechodových pravidel, která každému vnitřnímu stavu a k-tici vstupních znaků (z každého vstupního sledu jeden znak) přiřazují nový vnitřní stav a výstupní znak.
Výpočet stroje probíhá po krocích. Na začátku výpočtu je stroj v počátečním stavu a z každého vstupního sledu bude číst první znak. V jednom kroku stroj přečte z každého vstupního sledu po jednom znaku, podle vhodného přechodového pravidla (tj. podle svého programu) změní svůj vnitřní stav a zapíše nejvýše jeden znak na výstup. Výpočet končí v okamžiku, kdy neexistuje přechodové pravidlo, podle něhož by výpočet mohl pokračovat.
Nyní popíšeme sekvenční stroj ještě jednou formálněji.
Konečný sekvenční stroj s k vstupy je uspořádaná pětice
(V,Y,Q,f,q0), kde V,Y,Q jsou konečné množiny,
q0 je prvkem Q a f je
parciální zobrazení
Qx(VU
{_})k -> Qx(YU
{_}). Slovo
parciální znamená, že f nemusí být definováno pro všechny
kombinace stavů a vstupních symbolů (tzn. v takové situaci
není určeno, jak má výpočet pokračovat). Množina V se nazývá
vstupní abeceda, Y výstupní abeceda, Q je množina stavů, q0
je počáteční stav a f jsou přechodová pravidla. Speciální
hodnota _ použitá v definici přechodových pravidel znamená,
že v příslušném vstupním sledu už není žádný znak (celý
vstupní sled už byl přečten) resp. že se do výstupního sledu
v tomto kroku nic nezapíše.
Výpočet stroje začíná ve stavu q0 a vstupní sledy jsou nastaveny pro čtení prvních znaků. V každém kroku výpočtu stroj přečte po jednom znaku z těch vstupních sledů, které ještě nebyly přečteny do konce, vypíše jeden (případně žádný) znak do vytvářeného výstupního sledu a změní svůj vnitřní stav. Označme q momentální stav stroje a a1, a2...ak právě čtené znaky ve vstupních sledech (je-li některý vstupní sled již celý přečten, bude čteným znakem _). V přechodových pravidlech se vyhledá hodnota f(q,a1,a2...ak)=(q',y). Pokud je nalezena, stroj do výstupního sledu zapíše znak y a přejde do stavu q'. Pokud odpovídající přechodové pravidlo neexistuje, výpočet stroje končí.
Pomocí sekvenčních strojů budeme zpracovávat zápisy celých nezáporných čísel. Zápisem celého nezáporného čísla C v binární (dvojkové) poziční soustavě je sled znaků anan-1...a1a0 z abecedy {0,1} takový, že platí:
Pomocí sekvenčních strojů budeme nyní zpracovávat zápisy celých čísel v tzv. doplňkovém kódu. K zápisu čísel budeme používat abecedu {0,1}. Celá nezáporná čísla budeme zapisovat v obvyklé binární poziční soustavě s jedinou drobnou úpravou - zápis čísla musí začínat číslicí 0. Toho lze snadno dosáhnout doplněním jedné nebo více nul zleva k zápisu čísla. Každé celé nezáporné číslo má tedy nekonečně mnoho různých zápisů, které se liší pouze počtem úvodních nul.
Zápisy záporných čísel získáme následujícím postupem. Ze zápisu absolutní hodnoty čísla (v binární soustavě s vedoucí nulou) nejprve odečteme jedničku a potom zaměníme každou 0 za 1 a každou 1 za 0. Zápisy záporných čísel tedy začínají číslicí 1. I každé záporné číslo má více možných zápisů, ty se liší pouze počtem úvodních jedniček.