Zkouska 9.6. Topfer

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
biosek
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 9. 6. 2014 16:19
Typ studia: Informatika Bc.

Zkouska 9.6. Topfer

Příspěvek od biosek »

ZADANI:
Mame soubory. V kazdem souboru je clanek. Kazdy clanek se sklada z vet a vety se skladaji samozrejme ze slov. Chceme zjistit, co ve clankach jsou nejpopularnejsi slova. Kriterium zjisteni cetnosti jednoho slova je ale malo. Kriterium ze zadani bylo nalezt dvojice slov z vet, ktera se vyskytuji ve vsech clancich nejvice.

KOMPLIKACE:
-V ramci jedne vety napr. veta "A B A B A B." Se vyskyt dvojice "A B" pocita jen jednou.
-Soubor Synonym, kde na kazdem radku byli synonyma pro nejake slovo (nechceme prece brat jako ruzne dvojice "pes bouda" "psi bouda" "psa bouda" atd)
-Blacklist, kde na kazdem radku bylo jedno zakazane slovo. (prevazne spojky a sprostarny) Slova v blacklistu mohli take obsahovat synonyma!

VYSTUP:
50 nejcetnejsich dvojic slov

OMEZENI:
Pocet souboru <= 1000
Pocet slov v souboru <= 10 000
Pocet slov dohromady <= 1 000 000
Delka slova <= 20
Synonym pro slovo <= 20
Pocet ruznych slov <= 1 000 000
Pocet slov ve vete <= 30
Pocet slov v blacklistu <= 10 000
RAM PAMET 0,5MB
Disk neomezene


Me reseni: Nejdrive jsem si synonyma blacklistovych itemu dal do blacklistu, pak jsem slil clanky do jednoho souboru, odstranil blacklistovy slova ze souboru, zmenil slova ve vetach za jejich nejkratsi synonyma. Dale jsem soubor naformatoval tak, aby na kazdem radku byla jedna veta. Kazdy radek jsem sesortil unique (abych odstranil duplicitni slova ve vete, kdyz maji byt vice stejnych dvojic ve vete ignorovany). No a na konec jsem soubor s vetama prochazel a co to slo, tak jsem si vytvarel Dictionary<string,int> kde string byla dvojice z vety a cislo jeji cetnost. Do pameti se mi takhle veslo cca 50vet. Po naplneni pameti jsem ji vyprazdnil do souboru part_x ve formatu "slovo slovo pocet" na radku. A takhle jsem pokracoval az na konec souboru vet. Po projeti jsem mel soubory part_1 az part_k, ktery jsem jenom sesortil a mergnul do jednoho souboru (pri mergi jsem scital pocty), sesortil vysledny soubor sestupne (nebylo potreba asi) a prvnich 50 radek byl pozadovany vystup (bez tretiho sloupce poctu).
Odpovědět

Zpět na „PRG031 Programování II“