Zápočtový test 18.1.

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
vojta_vorel
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 14. 1. 2011 15:10
Typ studia: Informatika Ph.D.

Zápočtový test 18.1.

Příspěvek od vojta_vorel »

Zadání v příloze (nejspíš bude trvale taky na strákách Jozefa Jiráska).
Na první pohled hustý, na další pohledy taky, ale myslím že většina lidí to tam udělala.
Bylo nám řečeno něco ve smyslu: "Procházení všech možností je moc pomalé, ale jinak každá heuristika která vás napadne bude nejspíš ok".
Můj postup:
> vektor vektorů charů - stav věcí
> vektor slov
> vektor vektorů pointrů na chary ve stavu věcí - kolonky pro slova
> vektor intů - prmutace pi pořadí kolonek (heuristika- prostřídání svislých a vodorovných)
> vektor boolů - záznam o už použitých slovech
> přímé načtení vstupu do stavu, z něj detekce kolonek (zvlášť svislé, zvlášť vodorovné)
> rekurzivní fce s parametrem level (číslo), která si lokálně uloží kopii stavu a záznamu o slovech, najde všechny slova, která by šla v daném stavu nacpat do pi(level)-té kolonky a zkusí pustit fci na všechny takto upravené stavy, pokud některá vrátí true nebo je už vše plné, vrátí true. Jinak vrátí false a stav do původního stavu.

Ta heuristika je divná a určitě neefektivní, ideální by bylo, kdyby se každá zpracovávaná kolonka křížila s předchozí, rekurze by se pak fakt málo rozvětvovala. Mě to ty vstupy zpracovávalo tak 5 vtěřin.

přeju úspěch, Vojta
Přílohy
kriskros.zip
testovací vstupy
(2.12 KiB) Staženo 319 x
18_1_12.pdf
zadání
(125.75 KiB) Staženo 457 x
miso

Re: Zápočtový test 18.1.

Příspěvek od miso »

Je dobre si pre kazdy slot spocitat, kolko slotov ho krizi, potom si sloty zoradit zostupne podla tohto udaju a prechadzat ich zaradom. Takto to dava riesenie na vsetkych 6 vstupov maximalne za 0.5 sekundy.

http://uloz.to/xvmTShP/test3-zip
Odpovědět

Zpět na „NPRG041 Programování v C++“