Zkouska 30.5.2006

Medved
Admin(ka) level I
Příspěvky: 168
Registrován: 30. 5. 2006 21:18

Zkouska 30.5.2006

Příspěvek od Medved »

Tak jak to probihalo

Na zacatku si kazdy vylosoval svuj kratky program, presne jako v zimnim semestru. Na ten mel hodinu a vse bylo podle toho co, Kryl rikal na prednasce a co ma na svych strankach.
Ja mel destruktivni sjednoceni dvou usporadanych linearnich seznamu.

Druhy priklad bylo doslova vymezene zadani, bez jakekoliv moznosti vlastni kreativity, zkusim to nepomotat.
---------------------------------------------------
Na vstupu jsou dva textove soubory:
stranka.txt
dotaz.txt
V souboru stranka je maximalne 56000 slov, oddelenych jednim a vice whitespacy.
V souboru dotaz.txt je maximalne 100 slov. Kazde maximalne 100 pismen dlouhe. Na zacatku je jeste jejich pocet N (mensi nez tech 100)

Vasim ukolem je najit v souboru stranka.txt nejkratsi mozny usek, kde se danych N slov nachazi minimalne jednou a zjistit jeho delku.
Delka useku "ahoj jak se mas" je 15 nebo tak neco. Proste pocitaji se i mezery.
Na vystupu pak je na prvnim radku delka toho useku, na druhem pozice prvniho slova v souboru stranka, mysleno absolutni pozice slova mam pocit.
Na dalsich radcich jsou pak postupne slova tvorici hledanou posloupnost.
-----------------------------------------------------------------

Pameti je dost, jenom ji pouzivejte z rozmyslem. Nic moc vic k tomu nerekl.

Priklad byl vicemene jednoduchy, mel jsem ho asi za dve hodiny, pak jsem do toho jeste hodinu nudou cumel, neco proskrkal, ale fakt jednoduche.

Osm lidi slo na ustni hned dneska. Tam si precetl kratky priklad, dlouhy jsem mu viciemene vysvetlil, po nekolika minutach presvedcovani uznal ze algoritmus je dobre. Ale dalo to praci, je hrozne neodbytny a kdyz mi postopadesate rekl tojealekravina, tak uz mi nabihaly zily. DO tech papiru se potom letmo podival, ale kdyby tam byly kraviny, tak to ani nepozna.

Protoze priklad nebyl uplne na jedna (slabsi jedna), tak se me zeptal jeste na quicksort.
Chtel nejake definice asymp. slozitosti, prostorove slozitosti, o(n), v tom jsem plaval, uplne me vydeptal... a nakonec mi rekl at prijdu jindy jenom na teorii, ze budu bojovat jeste o dvojku, ale dneska at jdu.

Proste de<>.
Odpovědět

Zpět na „PRM044 Programování I“