99 Kezdőlap - Webszerkesztés - PHP - Legrövidebb út

Legrövidebb út

véletlenszerűen elhelyezkedő pontok között

Feladat

Hozzon létre egy képet, melyen megjelenít egy pontot középen, majd ezt követően még további néhány (minimum négy, maximum nyolc) pontot véletlenszerű helyen! A pontok helyét a további számítások elvégezhetősége céljából egy tömbben is tárolja le.


Tekintsünk úgy az ábrára, mint egy sematikus logisztikai térképre: jelentse a középső pont azt a helyet, ahonnan kiindulva minden további pontba el kell juttatni egy-egy csomagot, vagyis be kell járni a pontokat. Vizsgáljunk meg ehhez különböző bejárási lehetőségeket. Minden alább ismertetett bejáráshoz készítsen egy-egy ábrát az útvonal szemléltetése céljából!

1. Csillagtúra

Első lépésként határozza meg, mekkora utat jelent a bejárásnak az a módja, amikor a középpontból indulva sorra elmegyünk minden pontba, és azok mindegyikéből mindig vissza is térünk a kiindulási helyre a következő cél meglátogatása előtt. (Az egyszerűség kedvéért jelentsen 1 képernyőpont 1 km-nyi távolságot.)



2. Eredeti sorrend szerint

Következő lépésként számítsa ki, mekkora utat kell bejárni abban az esetben, ha a pontokat a létrehozás sorrendjében (vagyis az őket tároló tömbön belüli sorrend szerint) látogatjuk végig oly módon, hogy a központból elindulva az első pontba lépünk, majd onnan közvetlenül a másodikba, harmadikba, és így tovább, míg végül az utolsó pontból térünk csak vissza a középpontba!



3. Mindig a legközelebbihez

Optimalizáljuk az útvonalat: járjuk be úgy a pontokat, hogy a középpontból induljunk el a legközelebbi pontba, majd onnan rendre mindig a legközelebbi - de még be nem járt - pont irányába haladjunk tovább. Az utolsó pontból menjünk vissza a központba. Határozza meg az így bejárt út hosszát!



4. A legrövidebb út

Végül határozza meg a pontok bejárásához szükséges legrövidebb utat, és számítsa ki annak hosszát is. (Ennek megvalósításához - szükség esetén - tekintsen vissza a Permutáció című feladatra.)



Összegzés

A kapott eredményeket foglalja táblázatba! Ebben adja meg a felsorolt bejárások hosszát, valamint hogy az egyes bejárások hossza hány százalékos úthosszat jelent a leghosszabbnak számító csillagtúrához képest.

Bejárás módja Út hossza Út aránya
Csillagtúra 1065 km 100%
Eredeti sorrend szerint 657 km 62%
Mindig a legközelebbihez 657 km 62%
A legrövidebb út 657 km 62%


A feladat megvalósítását objektumorientáltan készítse el. Ennek keretében akár több osztályt is létrehozhat, például


2019-05-23 23:10:24 Admin Köszönöm, ha Ön lesz az első, aki megírja ide véleményét, észrevételét, kérdését ezzel a lappal kapcsolatban.




Új hozzászólás:
E-mail cím:


Erre a címre küldjük ki a hozzászólás jóvá- hagyásához szükséges linket. Az e-mail címet sehol nem tesszük közzé.

Név:


Ez a név fog megjelenni az Ön hozzászólásai mellett.

Mennyi tizenhat + hét?
Számjegyekkel írja be!



Ez a robotok beírása elleni védelem miatt szükséges ellenőrzés.


© infojegyzet.hu, 2018. március