zap 21.9.
Napsal: 22. 9. 2006 13:02
Tak tentokrat(a letos naposled) bylo zadani dost husty...aspon podle statistik, ktery mam od kamose(ja tam nebyl az do konce) z 19 lidi to dali dva(jeden po 3hodinach, ktery na to byly puvodne dany a jeden asi o hodinu dyl) a to i pres to, ze nekteri to zkouseli i cca 10 hodin, ano slovy deset hodin!:evil: No posudte sami, tady je zadani:
http://peklo.unas.cz/shakespeare.abc
http://peklo.unas.cz/shakespeare_small.out
http://peklo.unas.cz/shakespeare_small.tree
- Program pro formatovani binarnich stromu slov
=============================================
Program se bude spoustet z prikazove radky nasledujicim zpusobem:
tree x.tree
a vypise strom na standardni vystup. Vstupni soubor x.tree ma nasledujici
format:
1. radek obsahuje jmeno souboru se seznamem slov (napr. x.abc), ktery se
nachazi ve stejnem adresari jako x.tree a pro jednoduchost berte ze je vse v
current working directory.
2. radek obsahuje pocet slov ve slovniku x.abc (znacim by A), za nimz
(mezerou oddeleny) nasleduje pocet vnitrnich vrcholu (vcetne korene)
binarniho stromu. Znacim C.
Vyznam je takovy ze slova ve slovniku se cisluji od 1 do A (vcetne) a za
nimi nasleduji cisla vnitrnich vrcholu stromu (od A+1 do A+C vcetne).
Dale nasleduje presne C radku, na kazdem z nich jsou 2 cisla oddelena
mezerou, prvni je index leveho podstromu, druhy index praveho podstromu.
Takze kdyz tato cisla budou >A tak to znamena ze strom dale pokracuje
vnitrnim uzlem, kdyz budou <=A tak jsme v listu a podle souboru s abecedou
muzeme urcit ktery ASCII retezec reprezentuje danne slovo.
Koren slovu je na poslednim radku souboru *.tree a navic je tento soubor
usporadany v tom smyslu, ze pri pruchodu libovolnou vetvi od korene k listu
postupujeme v souboru vzdy jen nahoru.
Soubor *.abc obsahuje slovnik. Obsahuje A radku a na kazdem z nich je slovo.
Slovo na prvnim radku ma index 1, slovo na poslednim ma index A v cislovani
ve kterem se na slovnik odkazuje soubor *.tree. Pritom ve slove se muzou
vyskytnout libovolne znaky, krome '
'.
Nyni co ten program ma delat:
-----------------------------
Precte soubor *.tree a prislusny *.abc (kdyz nenalezne tak nejak
civilizovane zkonci). A potom vytiskne na standardni vystup ASCII-art
reprezentaci toho stromu. Nejprve to ukazu na priklade. Dejme tomu ze x.abc
obsahuje
slovo
veliceprevelicedlouhereklbychazpredlouheslovo
nejakedalsislovo
nepouziteslovo
a x.tree obsahuje
x.abc
4 2
2 1
5 3
Tak vysledek bude:
veliceprevelicedlouhereklbychazpredlouheslovo ++
slovo ----------------------------------------/|
nejakedalsislovo ------------------------------/
Bystrejsi z vas jiz pochytili ze jde o to vypsat leve vrcholy stromu vys a
prave niz a pospojovat je pri tom pomoci znaku - | / +
Pritom vetveni stromu se deje znakem + a objevuje se vzdy na leve (tedy
horni vetvi), takze se pise napr:
c ++ nebo pro jiny strom toto: c -+
a /| (1) a +/ (2)
b -/ b /
Tim padem mame vlastnost ze kdyz vyberu ze stromu nejaky uplny podstrom
ktery zacina na radku x a konci na radku y tak jeho koren bude vzdy na radku
x.
Dalsi vlastnost kterou nakresleni musi mit je, ze neplytva znaky `-', coz
znamena ze kdyz spojuju 2 jinak siroke podstromy tak doplnim jen nezbytny
pocet znaku `-' k uzsimu z nich (plati to i pro jednotliva slova). Krom toho
znak '/' se smi pouzivat jen kdyz se vetev zalamuje k nejakemu slovu. Neni
tedy dovoleno delat krive vetve ve stylu:
u -+--+
c ++ |
a /| / (3)
b -/ |
x ---/
Kontrola spravnosti bude probihat binarnim porovnanim souboru se vzorovymi
resenimi. To znamena ze zalezi i na mezerach a newlinech. Proto zduraznuji
ze za slovem nasleduje presne 1 mezera, pak je ten strom, ktery musi byt
zaplnen na celou sirku mezerami (viz priklad (2) kde nejnizsi list musi mit
mezeru na konci posledniho radku aby znaky zabiraly sloupec konstantni
sirky) a pak konci znakem '
' (M$-DOSovy '\r' tam tedy neni).
Napoveda:
---------
Da se to elegantne vyresit rekurzivnim pruchodem toho stromu, jen je potreba
ho delat 2* pri prvnim si spocitam jak budou ty veci velike abych pri druhem
vedel kolik mam kam psat minusu.
http://peklo.unas.cz/shakespeare.abc
http://peklo.unas.cz/shakespeare_small.out
http://peklo.unas.cz/shakespeare_small.tree