Je dáno celé číslo N (1<=N<=1000) a posloupnost N celých čísel. Napište program, který určí délku maximálního vybalancovaného úseku v dané posloupnosti čísel. Při návrhu programu se zaměřte na dosažení co největší rychlosti výpočtu.
Příklad: Pro N=10 a posloupnost čísel 8 6 4 7 -5 -3 2 0 -1 9 bude výsledkem číslo 7, neboť nejdelší vybalancovaný úsek 4 7 -5 -3 2 0 -1 (případně jiný stejně dlouhý vybalancovaný úsek 7 -5 -3 2 0 -1 9) je tvořen sedmi čísly.
P-III-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.
Silnici nazveme nepostradatelnou, pokud by se jejím zničením úplně přerušilo silniční spojení mezi některou dvojicí měst.
Napište program, který vyhledá a vypíše všechny nepostradatelné silnice. 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-III-3
Na hromádce je připraven předem známý počet N zápalek,
kde N je liché číslo. 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 1, 2 nebo 3 zápalky. Hra
skončí, když je celá hromádka zápalek rozebraná. Vyhrává ten
hráč, který z hromádky celkově odebral sudý počet zápalek.
Ří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 poziční soustavě o základu (-2) je sled znaků
anan-1...a1a0
z abecedy {0,1} takový, že platí:
C=an(-2(n+an-1(-2)n-1+...+
a1(-2)1+a0(-2)0
Jednotlivým znakům zápisu říkáme cifry. Takovýto zápis čísla
je strojem čten nebo je vytvářen postupně od nejvyšších řádů
(an) k nejnižším (a0).
Zápisem pozpátku rozumíme zápis cifer
v opačném pořadí. Čísla zapsaná pozpátku tedy stroj čte
v pořadí od nejnižších řádů (a0) k nejvyšším (an).
Uvědomte si, že popsaným způsobem lze zapsat libovolné celé číslo, a to až na úvodní nuly právě jedním způsobem.