Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2012-2013‎ > ‎

2. óra

Az első órán feladott probléma túlságosan nehéznek bizonyult, ezért nekiállunk a szükséges eszközök felépítésének.

Permutációk

A terv

A tologatós játék állapotai a tábla elrendezéséből és az elrendezéshez vezető lépésszámból fognak állni. Kezdetben nulla lépést tettünk meg, és a kiinduló helyzetben van a tábla. Ezt a keresési csomópontot egy sorba tesszük. Az algoritmus mindig kiveszi a sorból a következő állapotot, és annak összes rákövetkezőjét (ahova léphetünk belőle) beteszi a sorba, amennyiben az új csomóponthoz tartozó tábla állás még nem fordult elő.

A bejárt állások kezelésére felvehetjük az összes lehetséges permutáció rendezett listáját, amiben bináris kereséssel választhatjuk ki a kérdéses elemet.

További gyorsítása, ha az előbbi listát a permutáció rangjával (sorszámával) indexelt logikai tömbként valósítjuk meg.