23.01.2017

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

23.01.2017

Příspěvek od PeterP »

Ahoj,
zadanie bolo nájsť najkratšie riešenie Loydovej 15tky, ale s rozmermi 3x3.

Bolo treba odlíšiť riešiteľný a neriešiteľný vstup.
Potom zadával nejaké vstupy (nepamätám si aké konkrétne):
1) počet krokov mal byť 31
2) 32
3) nemalo riešenie

Úspešnosť:
v riadnom čase to dali asi 3, na konci po predĺžení o 45 min. 5/17. Dvaja alebo traja mali ešte mail poslať.

Osobne som to vyriešil cez heuristiku (počet zle uložených políčok + počet ťahov). Načítal som si vstup a z neho generoval ďalšie stavy, ktoré som vkladal do prioritnej haldy a vyberal som stav s najmenším ohodnotením.
marek094

Re: 23.01.2017

Příspěvek od marek094 »

Ahoj,
správným řešením byla modifikace BFSka, kde vrcholy byly rozložení 3x3 mřížky. BFS se zastaví až dojde do mřizky {{1,2,3},{4,5,6},{7,8,0}}

Mřížka se dala třeba reprezentovat pomocí bitových operací/polynomu v unsignedlonglongu.
Tohle číslo se dá použít třeba do unordered_map na pamatování si tahů.
Pro zjednodušení se hodí napsat si funkce, které z čísla mřížky vyrobí neco jako array<array<int,3>,3> a naopak.
Zdroják jsem si zapomněl schovat.
vasek.rozhon
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 25. 1. 2017 16:34
Typ studia: Informatika Bc.

Re: 23.01.2017

Příspěvek od vasek.rozhon »

Ahoj,

já jsem si taky zapomněl schovat zdroják :-D. Jak již bylo nicméně řečeno, stačí si to představit jako procházení grafem, pak kupříkladu BFS. Jednotlivé stavy jsem si ukládal jako stringy, pak je potřeba jen vyřešit, jak se z jednoho stavu dostat do druhého (existují čtyři hrany) a ukládat si, kde jsem už byl. (v mém případě to byl unsigned_map<std::string, std::pair<std::string, int> >, tedy jsem si pro každý stav ukládal jeho vzdálenost od počátku a jeho předchůdce v BFS stromě pro rekonstrukci cesty).

Mimochodem, ten člověk (Přemysl Čech) byl hodně hodný a na kód koukal jen tak letmo - alespoň u mě jen ověřil, že to má hlavu a patu (a je to napsané v C++ :-D) a dal to vyzkoušet na několika vstupech.

Pokud byste si to někdo chtěli nakódit, tak pro půlku vstupů to nejde (záleží na znaménku permutace), pro tenhle vstup do jde asi na 31 tahů (což je nejhorší případ). Mělo by to seběhnout tak do vteřiny (=>ve Visual Studiu v debug módu do minuty :-D).

8 6 7
2 5 4
3 1
karamel
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 1. 2017 16:30
Typ studia: Informatika Bc.

Re: 23.01.2017

Příspěvek od karamel »

Ahoj, narazil jsem na oficiální zadání, tak ho sem přidávám
Přílohy
LoydPuzzle.pdf
Zadání úlohy
(348.36 KiB) Staženo 307 x
Odpovědět

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