S 120. Horcsin Bálint 9. évf. Budapest, Németh László Gimnázium Fordtó program: Java 8, Fejlesztői környezet: NetBeans 8.2 A program elvi menete: Nézzük az eredeti gráfot! Minden ponthoz rendeljünk hozzá két számot: 1. érték > Ha csak a tőle kívüleső pontokat(1) és őt vesszük, akkor a megtehető utak maximális száma. 2. érték > A fenti utak megtétele után a megállóban lévő utasok száma. Ezeket az értékeket ki tudjuk számolni, ha a kívüleső pontokra ezeket az értékeket ismerjük (ezt a Pont objektumok update() algoritmusa végzi el). Amennyiben egy ponton kívüleső összes pontot kiszámoltuk, akkor már csak egy (vagy 0) vele összekötött pont nincsen kiszámolva a feladat alapján. A frissítésekből kihagyjuk az 1. megállót, és a többbivel elvégezzük ezeket, amíg az összes nem frissül. Ezek után végezzük el az ellenőrzést az 1-essel, aminek ez az algoritmusa kis mértékben módosítva van (InduloUpdate()). Ezek után az 1. pont 2. érték. (1) Ezek azok a pontok, amelyekre való eljutáshoz nem kell használni a viszonyítási ponttól az 1. ponthoz szükséges legrövidebb út szakaszait. Algoritmusok, osztályok rövid, fontosabb változók részletes áttekintése: s120 osztály: Algoritmusok: -public static void main(String[] args): Itt történik a beolvasás, az adatok tárolása és a program többi részének irányítása. A program működési elve máshol van. Pont osztály: Ennek egy-egy osztálya egy-egy megállót (pont a gráfban) jelöl. Fontosabb változók: - int[] kapcs: A megálló többi megállóval lévő kapcsolatai (azok sorszámával). - private int hany: A megállóban eredetileg álló utasok száma. Másik objektumnak, static-us algoritmusnak nem kell hozzáférnie, maga az objektum kiszámolja a szükséges adatokat. - static Pont[] pontok: Az osztály összes objektumát tartalmazó tömb. Megjegyzés: Az 1. megálló a 0. helyen, a 2. megálló az 1. helyen stb. van. - static boolean tortent: Az updateAll() ellenőrző változója. - boolean mar: Az objektum két értéke ki van-e számolva - int eddig: Ha csak a tőle kívüleső pontokat(1) és őt vesszük, akkor a megtehető utak maximális száma. - int publichany=0: A fenti utak megtétele után a megállóban lévő utasok száma. Algoritmusok: - public Pont(int hanyan, int[] kapcsolat): (Constructor), Pont létrehozása - public void update(): A megálló két értékének kiszámítása. A program legfontosabb, legbonyolultabb része. - public void InduloUpdate(): Az első megállóhoz tartozó az update() algoritmus kis mértékben módosított változata. Ez a program egyik utoljára használt függvénye. - static boolean updateAll(): Az összes objektummal (kivéve 1. megálló) végrehajtja az update() algoritmust. Megjegyzés: A tortent (static boolean tortent) változó értékével tér vissza. Algorimusok részletes menete: s120 osztály: Algoritmusok: - public static void main(String[] args): - Beolvasás, eltárolás. - Útvonalkeresés (Pont.updateAll() függvény többszörös elvégzése). - Kiindulóállomás kiszámolása. - Kiindulóállomás 1. értékének kiírása. Pont osztály: Algoritmusok: - public Pont(int hanyan, int[] kapcsolat): (Constructor), Pont létrehozása. - public Update(): - Gondolatmenet: Minden tőle kívüleső szomszédosba el kell jutni. Ha ez nem megy, akkor a legértékesebb (legmagasabb eddig értékkel rendelkező) mezőkbe kell eljutni. - Ha nincs még az objektum értéke kiszámolva és az összes től kívüleső megálló ki van számolva: - Ha el tud jutni az összes mellette lévő megállóba, amelyik tőle kívül esik: - A legértékesebb (legmagasabb eddig értékkel rendelkező) mezőkbe megy el. - különben: - Az összesbe elmegy egyszer, és a maradékkal oda-visszamegy. - public InduloUpdate(): - Gondolatmenet: Minden tőle kívüleső szomszédosba el kell jutni. Ha ez nem megy, akkor a legértékesebb (legmagasabb eddig értékkel rendelkező) mezőkbe kell eljutni. - Ha nincs még az objektum értéke kiszámolva és az összes től kívüleső megálló ki van számolva: - Ha el tud jutni az összes mellette lévő megállóba, amelyik tőle kívül esik: - A legértékesebb (legmagasabb eddig értékkel rendelkező) mezőkbe megy el. - különben: - Az összesbe elmegy egyszer, és a maradékkal oda-visszamegy.