I/S. 20 Horcsin Bálint 9. évf. Budapest, Németh László Gimnázium Fordító program: Java 8, Fejlesztő környezet: NetBeans 8.2 -------------------------------------------------------------------------------- Megoldás elvi menete: A négyzetháló kinégyzeteinek adatait beolvassa, és eltárolja őket Egyseg objektumokként. Az Egyseg osztálynak van egy két dimenziós tömbje, amely földrajzi elhelyezkedés szerinti sorban tárolja az Egyseg objektumokat. Minden egyes Egyseg objektum tartalmaz egy update() metódust és egy "toltes" értéket. A "toltes" érték azt jelenti, hogy abból a négyzetből mennyi energiára lenne szüksége a kocsinak a célbajutáshoz, ez a futás végére lesz csak helyes, azelőtt folyamatosan csökkentve lesz. Az érték csökkentését az update() algoritmus végzi el. Ez az algoritmus a szomszédos négyzetek "toltes" értékéből, magasságából és az aktuális objektum magasságából meghatározza az éppen aktuális legkisebb lehetséges értéket az aktuális objektum "toltes"-ére. Az Egyseg osztály updateAll() algoritmusa az összes objektummal az update() algoritmust és ezt a program központi része elvégzi, ameddig történik emiatt változás. Ezek után a program központi része kiírja a start pontból a végpontba való eljutáshoz szükséges legkevesebb energiát (a start ponthoz tartozó Egyseg objektum "toltes" értékét). -------------------------------------------------------------------------------- Osztályok rövid leírása: -is20Main: A programot ez irányítja, beolvasásokat, kiírásokat ez végez el, viszont a legfontosabb rész nem itt megy végbe. -Egyseg: A Egyseg egy-egy objektuma gyakorlatilag a négyzetháló egyik négyzete. A program legfontosabb részét ez az osztály végzi el az updateAll() algoritmus az objektumok update() algoritmusa segítségével. -------------------------------------------------------------------------------- Az algoritmusok rövid leírása: is20Main osztály: - public static void main(String[] args): A programot ez irányítja, beolvasásokat, kiírásokat ez végez el, viszont a legfontosabb rész nem itt megy végbe. Egyseg osztály: - public Egyseg(int x, int y, int magassag): Létrehoz egy Egyseg objektumot adott helyen, adott magassággal és elhelyezi az osztály ek változójában a létrejött objektumot. - public void update(): A szomszédos egységek töltöttségei alapján az aktuális objektum töltését a lehető legkisebbre állítja. - public void updateAll(): Végig megy az összes objektumon és frissítteti velük a szomszédos egységek töltöttségei alapján az ő töltésüket -------------------------------------------------------------------------------- Az algoritmusok részletes menete: is20Main osztály: - public static void main(String[] args): - Adatok darabszámát meghatározza. - Létrehozza a Sziget Objektumokat az adatok beolvassal egybekötve. - Bekéri a kezdő és végpontokat. - Kiszámoltatja az Egyseg osztállyal az utakat. - Kiírja a cél Egyseg "toltes" értékét. Egyseg osztály: - public Egyseg(int x, int y, int magassag): Létrehoz egy Egyseg objektumot adott helyen, adott magassággal és elhelyezi az osztály ek változójában a létrejött objektumot. - public void update(): - kiszámolja mind a négy irányból, hogyha arra felé menne onnan, akkor ahhoz mennyi energia kellene - Megkeresi ezek közül az értékek közül a legkisebbet, és ezzel folytatja a következő műveletet: - Ha ez kisebb, mint 1, akkor 1-re állítja, mert "Az autó nem tud továbbmenni, ha egy négyzetbe érve nem pozitív az energiája, ezért az csak a cél négyzetben lehet 0." - Ha ez kisebb, mint az objektum "toltes" értéke, akkor ezt beállítja annak, és az updated logikai változót igazra állítja. - public static boolean updateAll(): - Végig megy az összes objektumon és frissítteti velük a szomszédos egységek töltöttségei alapján az ő töltésüket. - Visszatér egy logikai változóval, ami arra ad választ, történt-e változás -------------------------------------------------------------------------------- Megvalósítás sajátosságai: A megoldásomnál kiemelten fontos volt egy objektum orientált programozási nyelv használata, mivel sok mindent más, nem objektum orientált programozási nyelvvel (pl. C) nehéz lett volna megcsinálni a különféle adatok tárolását. A megoldás útvonal-keresési mechanizmusa részben a legtöbb pathfinder (útkereső) (pl. A*) algoritmus alapjára épült.