27.01. zápočtový test

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.
luki215

27.01. zápočtový test

Příspěvek od luki215 »

Dnešní zadání ve zkratce:

Máte kupu bodů s n-dimenzionálními souřadnicemi - databáze a druhou kupu bodů s n-dimenzionálními souřadnicemi - dotazy a číslo k. Pro každý bod z dotazů chcete vypsat k nejbližších bodů z databáze.

Vzdálenost "nejbližších" vyjadřovala metrika - program měl být napsán tak, aby bylo možno lehce přepnout na / přidat jinou metriku, museli jsme naimplementovat L2 a Cos metriky.

Zadání podrobně: http://siret.ms.mff.cuni.cz/cech/cpp/kNN.pdf
Mé řešení + zadání kdyby se nahoře smazalo https://1drv.ms/f/s!AviL0xDCNkBWgeQZk7zrd6MOl7Q01Q

Jaká byla úspěšnost nevím, ale myslím, že docela vysoká. Odevzdával jsem jako 4 už asi půl hodiny před koncem.
karamel
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 1. 2017 16:30
Typ studia: Informatika Bc.

Re: 27.01. zápočtový test

Příspěvek od karamel »

Tak ještě přiložím oficiální testovací data.

Soubor databaze.csv je seznam bodů, ve kterých hledáme K nejbližších bodů pro každý bod–dotaz v souboru najdi.csv:
https://mega.nz/#F!Ew4EnDwQ!Ht1jpw8ydCXuB-IgwkmCwA

Své řešení jsem neukládal, ale bylo poměrně jednoduché. Nemuseli jsme nějak přehánět efektivitu programu, stačilo tedy ke každému bodu najít jeho vzdálenost od dotazu, podle toho body seřadit a vypsat K prvních. Na těchto testovacích datech mi asi 200 řádků dotazů v debug módu běželo asi deset minut, v release módu to přežvýkalo všechny dotazy za pár vteřin.

Motivace a celkově zadání mi připadalo trochu odstrašující, ale když si člověk uvědomí, co má za úkol, není to vlastně moc těžké.
Odpovědět

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