První série dvacátého třetího ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
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ů)
Zahradní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ů)
Ada 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ů)
V 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 a !. 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:
alnum | písmeno nebo číslice |
alpha | písmeno |
blank | prá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) |
graph | tisknutelný znak kromě mezery (písmena, čísla, interpunkce, …) |
lower | malé písmeno |
print | tisknutelný znak včetně mezery |
punct | tisknutelný znak mimo písmena, čísla a mezeru |
space | bílý znak (mezera, nový řádek, tabulátor, …) |
upper | velké písmeno |
xdigit | hexadecimá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ě a, b, c.
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í