První série dvacátého třetího ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 18. října 2010 8:00. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

Milý deníčku,

oproti minulému týdnu, kdy jsem slavila osmé narozeniny a dostala hříbě, byl tenhle strašný. Matka mi sehnala nového učitele matematiky, který je ještě ošklivější než ten předchozí. Navíc se jí prý mám věnovat o dvě hodiny týdně víc.

Už takhle skoro nedělám nic jiného. Moc ráda bych teď, když umím flétnu, začala hrát na klavír a slečna Jane, naše komorná, mi nabídla, že mě to naučí, ale matce se to nelíbilo, že prý mi sežene pořádného učitele, ale že mám na hudbu dost času.

Včera se mi povedlo utéct z domu a zašít se s Charliem do dílny. Měl tam schovanou žábu. Povídal mi, že od svého táty, našeho zahradníka, slyšel, že můj táta válčí v Řecku. Přišlo mi to divný, ale prý to ví fakt určitě.

Zítra mě čekají nerovnice. Netěším se.


23-1-1 Básníkův deník (9 bodů)


Jednoduchá úlohaZahradníkův syn měl pravdu: otec naší hrdinky, slavný romantický básník lord Byron, se na začátku roku 1824 skutečně účastnil Řecké války za nezávislost na Otomanské říši. Jako záminku (či, chcete-li, motivaci) pro první úlohu nového ročníku našeho semináře si vezmeme jeho deník, ve kterém popisoval své výlety a cesty Řeckem předtím, než 19. dubna umřel.

Řekněme, že si každý večer před spaním zaznamenal, o kolik metrů níže či výše za uběhlý den sestoupil či vystoupil. Váš program dostane seznam těchto údajů (jedno celé číslo za každý den) na vstupu a vaším úkolem je vypsat dvě čísla:

  • V jaké výšce se lord Byron na konci každého dne nacházel nejčastěji? Je-li více možných odpovědí, vypište libovolnou z nich.
  • V jaké největší nadmořské výšce jeho lordstvo přenocovalo?

Předpokládejte, že putování začalo u mořské hladiny (této výšce přiřadíme, jak je zvykem, nulu), a nikdy pod mořskou hladinu nesestoupilo.

Příklad vstupu: 103 20 -20 50 -82
Odpovídající výstup: nejčastěji: 103, nejvýše: 153

Řešení

Vážený pane de Morgane,

jsem vám velice vděčna, že jste si i na cestách našel čas a sepsal mi obsáhlý dopis plný úloh, jejichž řešením se poslední dva týdny těším. Vězte prosím, že matematiku studuji stejně pilně jako pod Vaším laskavým dozorem a že až na den mých patnáctých narozenin nebyla má pozornost odvedena od počtů ničím zásadním.

V příloze vám zasílám některé výsledky a upřímně doufám, že v nich nejsou ony trapné numerické chyby, které mne poslední dobou tak pronásledují.

S netrpělivostí v srdci vyhlížím váš návrat,

Ada


23-1-2 Jedna geometrická (10 bodů)


Z množství fiktivních úloh od pana de Morgana vybíráme dvě takové, které dává smysl zpracovávat moderní výpočetní technikou.

Mějme v kartézské soustavě souřadnic zadány body, jejichž souřadnice obecně nemusí být celočíselné. Ptáme se na nejmenší kruh, který je všechny obsahuje – tedy kde je jeho střed a jaký má poloměr.

Příklad vstupu: [0;0] [0;1] [1;0] [2;2]
Odpovídající výstup: S=[1;1], r=1.4142135

Řešení


23-1-3 Jedna maticová (11 bodů)


Na vstupu dostaneme matici, tj. dvojrozměrné pole celých čísel, která má navíc tu zvláštní vlastnost, že jsou čísla v každém jejím řádku a sloupci ostře rostoucí. Potřebovali bychom rychle zjistit, zdali v ní neexistuje nějaké políčko v i-tém řádku a j-tém sloupci, které by mělo hodnotu přesně i+j.

Pokud hledaných políček existuje víc, můžete vypsat libovolné z nich. Pár bodíků navíc si můžete vysloužit, pokud vymyslíte, jak rychle spočítat, kolik takových políček je.

Při zvažování časové složitosti nepočítejte dobu načítání: představujte si, že už máte matici v paměti. Zkuste zdůvodnit, proč nelze dosáhnout rychlejšího řešení.

Příklad vstupu:

        -3  1  4
         4  5  6
         7  9 11
Odpovídající výstup: 1. řádek, 3. sloupec

Příklad vstupu:

         3  4  5
         4  5  6
         5  6  7
Odpovídající výstup: žádné takové políčko není

Řešení


23-1-4 Ale co trapné numerické chyby? (10 bodů)


Praktická CodExová úlohaAda však evidentně s matematikou pomoct nepotřebuje: trápí ji trapné numerické chyby. Mohli byste jí pomoci s tím? Třeba… s dělením?

Na vstupu dostanete dělence a dělitele a váš program by měl na výstup vypsat celý desetinný rozvoj podílu. Pokud je rozvoj nekonečný, vyznačte nejkratší možnou periodu.

Příklad vstupu: 1 2
Odpovídající výstup: 0.5

Jiný příklad: 1 3
Výstup: 0.(3)

Ještě jeden příklad: 143 56
Výstup: 2.553(571428)

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

Vážený pane Babbagei,

mrzí mne, že Vás zdržuji od důležité práce, ale naše setkání na zahradní slavnosti u pana Dickense mi nedá spát. Byla jsem Vám představena paní Somervillovou jako Ada, plným jménem jsem Augusta Byronová.

Je mi teprve sedmnáct let, ale má matka mi zajistila dobré matematické vzdělání a Vaše myšlenka Diferenciálního stroje, který by zautomatizoval výpočty matematických a technických tabulek, mi přijde úchvatná a podivně samozřejmá.

V příloze Vám zasílám seznam dokumentů a knih, o kterých od paní Somervillové vím, že je vlastníte, a o kterých doufám, že byste mi je, samozřejmě za patřičnou protislužbu, mohl zapůjčit.

Velice ráda bych se s Vámi též opět setkala osobně.

Zdraví

Augusta „Ada“ Byronová


23-1-5 Adina knihovna (10 bodů)


Velká zásilka knih od pana Babbageho co nevidět přijde, Ada si proto musí udělat pořádek v knihovně a uvolnit pro ni zvláštní police. Trvá jí to samozřejmě předlouho, každé zařazení publikace do správné poličky se neobejde bez zběžného projití až pročtení jejího obsahu.

Jakmile to Ada dodělá, napadne ji následující logická hříčka, nad kterou stráví zbytek večera:

Mějme řadu N knih správně seřazenou podle svého názvu (který má každá kniha různý). Nyní ji přeskládáme tak, aby každá knížka byla na pozici právě o K větší nebo menší, než byla po seřazení. Pro jaká K v závislosti na N jde něco takového udělat a kolika způsoby?

Řešení

(adresováno Charlesi Babbageovi)

Drahý příteli,

v příloze vám zasílám finální text překladu Menabreaova textu společně s poznámkami, na kterých jsme se dohodli. Věnujte prosím pozornost znění popisu výpočtu Bernoulliových čísel, opět jsem do toho hrábla, doufám, že nyní už bez újmy na matematické přesnosti.

Mým dětem se daří dobře, děkuji za optání. Byron už dorůstá do věku, kdy se musím rozhodnout, zdali ho hodlám obtěžovat matematikou, nebo jeho vzdělání nechám obvyklejší humanitní tvar. Je to těžké rozhodování a budu potřebovat Vaši radu.

Ráda bych Vás tu v Ockhamu zase někdy viděla. S mou finanční podporou samozřejmě můžete nadále počítat. Oba víme, kde by peníze, které bych Vám upřela, skončily.

Vaše Ada


23-1-6 Babbageova cesta (10 bodů)


Z posledního dopisu vidíme, že Babbage nemá peněz nazbyt. Samozřejmě se chce za paní Adou, hraběnkou z Lovelace, dostat v co nejkratším čase, ale ze všech možností, ze všech tras, které mu dosažení tohoto nejkratšího času nabízejí, potřebuje vybrat takovou, která je nejlevnější.

Na vstupu dostaneme dopravní mapu Anglie zadanou jako seznam spojení (železničních tras), které vedou mezi různými městy (vždy oběma směry). Pro jednoduchost předpokládejme, že použití takového spojení trvá jednotkový čas. U každého spojení je na vstupu také napsáno přirozené číslo, kolik pana Babbage jeho použití stojí. Také dostanete napsáno, ve kterém městě Babbage začíná a kde bydlí Ada.

Na výstupu vypište posloupnost spojení (neboli cestu), která ze všech cest z Babbageho stanoviště do Adina bydliště, které používají nejméně spojení, stojí nejméně peněz, tj. součet ohodnocení všech spojení na cestě je nejmenší. Pokud je takových cest víc, vypište libovolnou z nich.

Řešení

Ada zemřela v 36 letech na rakovinu dělohy. Nechala za sebou tři děti, které už jsou samozřejmě také dávno mrtvé, a první počítačový algoritmus, který by prý na Analytickém stroji, Babaggeově vylepšené verzi stroje Diferenciálního, skutečně běžel a generoval Bernoulliho čísla.

Vedou se neplodné diskuse o tom, nakolik byl program jejím dílem a nakolik šlo o práci Babbage, který toliko obdivoval její slohové schopnosti. Ada sice jeho snažení podporovala značnými částkami, stejně nemalé peníze ale prohýřila v sázkách na koně. Ke svým dětem prý měla ambivalentní vztah – Diferenciální stroj však považovala za „přítele“.

Sterling s Gibsonem kolem její postavy sepsali steampunkový román Mašina zázraků. Po Adě se jmenuje relativně použitelný programovací jazyk. Ada je skvělá. Ada je krásná. Ada je děvče všech matfyzáků bez děvčat.


23-1-7 Regulární výrazy (14 bodů)


SeriálV letošním ročníku si budeme povídat o regulárních výrazech. Už se vám jistě někdy stalo, že jste potřebovali nějak zběsile přejmenovat soubory, nahradit v textu všechny výskyty jména Markéta za jméno Dominika nebo jednoduše najít všechna slova začínající velkým písmenem. Dokud jsem nevěděl o regulárních výrazech, dělal jsem veškerou takovou práci ručně, což není od deseti stran nic příjemného, nehledě na to, že lidské oko často nějaký výskyt opomene…

K nalezení všech pádů jména Markéta v jednotném čísle by tedy například sloužil výraz Markét(a|y|ě|u|o|ou).

Regulární výraz umožňuje definovat množinu řetězců, které mu vyhovují. Když pak pomocí něj vyhledáváte, najdete všechny řetězce z té množiny.

Jak takový regulární výraz vypadá? Je to řetězec poskládaný z obyčejných a speciálních znaků. Typickým obyčejným znakem je písmeno: výrazu ab vyhovuje jen řetezec ab. Obyčejný znak je obecně „všechno ostatní“, tedy všechny znaky, o kterých si neřekneme nic zvláštního.

První důležitá skupina speciálních znaků, kterou si uvedeme, jsou znaky, které určují, kolikrát se předchozí znak bude opakovat:

*libovolný počet (0 …∞)
+alespoň jednou (1 …∞)
?jednou nebo vůbec
{n}právě n-krát, kdy n je přirozené číslo
{a,b}a- až b-krát, přičemž musí platit, že a ≤ b < K, kde K je číslo závislé na systému, obvykle 256, ale může být i víc. Pravá mez (b) může být i vynechaná. Pak je považována pravá mez za nekonečnou, nebo se to chová, jako by tam bylo K-1: to také záleží na systému.

Takže výrazu ab* vyhovuje řetězec, který začíná a a následuje libovolné množství b; výrazu a+b?c+ vyhovuje řetězec, který začíná alespoň jedním a, pak v něm možná je b a končí alespoň jedním c. Výraz d{3,5} je ekvivalentní s výrazem dddd?d?, neboť oběma vyhovují právě řetězce obsahující 3, 4, nebo 5 d.

Opakovat jen jeden konkrétní znak by však bylo hloupé. Můžeme tedy nějaký kus výrazu uzávorkovat do kulatých závorek a k němu celému se pak tenhle opakovací operátor bude vztahovat: výrazu (aa)* vyhovuje řetězec obsahující sudý počet a (ve stejném smyslu se dá použít a{2}*). Výrazu b?(ab)*a? vyhovuje řetězec, ve kterém se a a b pravidelně střídají. Výrazu b?(a+b)*a* pak vyhovuje řetězec složený z a a b, ve kterém se nikde nevyskytuje dvojice b vedle sebe.

Pomocí závorek můžeme také dát více variant za použití znaku | – výrazu (bagr|kombajn) vyhovuje jak řetězec kombajn, tak řetězec bagr (a nic jiného). Pozor, pokud napíšete (a|b){2}, budou výrazu vyhovovat řetězce aa, bb, ale i ab a ba. Opakovací operátory musíme brát jen jako zkratku za nakopírování toho, co opakují, vedle sebe do výrazu.

Úkol 1 [2b]

Napište jiný výraz, kterému budou vyhovovat přesně stejné řetězce jako výrazu b?(a+b)*.

Úkol 2 [2b]

Určete, které všechny řetězce vyhovují výrazu ((ab?)+|(ba?)+)*, a případně nalezněte kratší ekvivalentní výraz.

Další trik, který si v tomto díle ukážeme, jsou hranaté závorky. Do nich uvedeme množinu znaků, které se na tomto místě mohou objevit. Tedy výrazu [aZ!]* vyhovují řetězce jakékoli délky, které jsou složené pouze ze znaků a, Z!. Do závorek je možno uvést i rozsah: Výrazu [a-z] vyhovuje jakékoli malé písmeno. Také je dovnitř možno uvést třídu znaků: třeba [[:digit:]] jsou všechny číslice – standardní je následující dvanáctice:

alnumpísmeno nebo číslice
alphapísmeno
blankprázdný znak (obvykle mezera nebo tabulátor)
cntrlřídící znak (znaky s ASCII kódem menším než 32 a ještě pár dalších)
digitčíslice (0–9)
graphtisknutelný znak kromě mezery (písmena, čísla, interpunkce, …)
lowermalé písmeno
printtisknutelný znak včetně mezery
puncttisknutelný znak mimo písmena, čísla a mezeru
spacebílý znak (mezera, nový řádek, tabulátor, …)
uppervelké písmeno
xdigithexadecimální číslice ([0-9a-fA-F])

Třídy znaků je možno kombinovat: Výrazu [[:digit:][:lower:]XYZ.] vyhovují všechny číslice, malá písmena, X, Y, Z a tečka. Třídu můžeme také znegovat, uvedeme-li před výčet znaků stříšku ^: výrazu [^abc] vyhovují všechny znaky kromě abc.

Takovou perličkou je pak výraz, kterému vyhovují znaky ], ^ a -. Pomlčka totiž musí být na začátku nebo na konci, jinak signalizuje výčet; stříška nesmí být na začátku, jinak signalizuje negaci, a ] musí být na začátku, jinak signalizuje konec závorky: []^-] je správné řešení problému.

Může se hodit ještě jedna zkratka: tečka . symbolizuje jakýkoli znak. Oblíbený výraz .* pak symbolizuje libovolný řetězec.

Úkol 3 [4b]

Napište výraz, kterému budou vyhovovat právě desítkové zápisy čísel dělitelných osmi (takže 0, 8, 256, 344 vyhovují, ale 42 ani 37 ne).

Úkol 4 [2b]

Určete, které řetězce vyhovují výrazu (00)*[01](11)*.

Úkol 5 [4b]

Tomuto výrazu měly původně vyhovovat všechny řetězce, které mají sudý počet nul i sudý počet jedniček (a neobsahují jiné znaky). Nalezněte protipříklad a zkuste výraz opravit tak, aby dělal to, co má: (00|11)*(0(11|00)*1(11|00)*){2}

Tip: Existují dva typy protipříkladů na regulární výrazy: false positive je řetězec, který vyhovuje, i když by neměl; false negative je řetězec, který nevyhovuje, ale měl by. Druhý z nich je obvykle závažnější, první z nich se špatně hledá, zvláště v rozsáhlejších výrazech.

Pokud chcete použít jakýkoli speciální znak v jeho obyčejném významu, předřaďte před něj \ – výrazu \.\*\\ vyhovuje tečka následovaná hvězdičkou a pak zpětným lomítkem.

Ještě by se hodila poznámka, že tohle všechno zde vyložené jsou POSIX extended regular expressions, neboli rozšířené regulární výrazy. Existuje totiž mnoho dalších dialektů regulárních výrazů, něco víc si o nich povíme příště.

Mnoho programů vyhledává v textu po řádkách, typicky grep vypisuje všechny řádky, na nichž našel vyhovující řetězec. Existují tedy speciální znaky pro přišpendlení řetězce na začátek (^) nebo konec ($) řádku, takže výrazu ^...$ vyhovují právě tříznakové řádky a výrazu ^a vyhovují všechna a na začátku řádku. Tyto znaky mohou být použity jen na úplném začátku, resp. konci výrazu, kdekoli jinde jsou použity chybně. Takže výraz (a|^b$|c) je chybný…

Nakonec, kde se vlastně s regexy (což je zkratka z regular expressions) setkáme? S jejich pomocí vyhledávají slavné editory Vim i Emacs, na Windowsech třeba PSPad. Denním chlebem jsou pro programátora v Perlu a taktéž program grep a další využívají regexy ke svojí běžné činnosti. Konkrétně pak egrep používá přesně ten formát regexů, kterým jsme se tu zabývali.

Regexy můžete používat i v drtivé většině programovacích jazyků od C přes C# až k Perlu a Pythonu – někde jsou přímo součástí jazyka, jindy k dispozici jako knihovna…

Řešení