Toplista
- betöltés...
Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Fejtörő 7
Lackner Nóra
{ Polihisztor } kérdése
386
Egy bolhát elejtettünk egy Descartes féle koordinátarendszer fölött. A szerencsétlen meg akar szökni, de nem túl szellemes így az elején választ egy irányt (É, D, K vagy Ny) és azután csak abban az irányban halad, valamint tudjuk, hogy minden időegységben egy szomszédos rácspontra ugrik át. Szeretnénk ismét befogni! Ennek érdekében minden időegységben választhatunk egy rácspontot és ha a bolha pont azon a rácsponton tanyázik, akkor befogtuk, ha nem, akkor tovább próbálkozhatunk. Be tudjuk-e fogni a bolhánkat, vagy inkább keressünk egy kutyát?
(Ha nagyon nem megy, akkor pár tipp:
1. Egyszerűsítsd a feladatot úgy hogy mondjuk biztosan É-nak indul a bolha
2. Ha így sem megy, akkor próbáld koordinátarendszer helyett számegyenessel
3. Ha még így is nehéz, akkor próbáld számegyenesen egy adott iránnyal
4. A legegyszerűbb forma, ha csak fél számegyenessel dolgozol (0, 1, 2, ...) és a bolha valahonnan indulva fölfelé ugrál a számokon)
(Ha nagyon nem megy, akkor pár tipp:
1. Egyszerűsítsd a feladatot úgy hogy mondjuk biztosan É-nak indul a bolha
2. Ha így sem megy, akkor próbáld koordinátarendszer helyett számegyenessel
3. Ha még így is nehéz, akkor próbáld számegyenesen egy adott iránnyal
4. A legegyszerűbb forma, ha csak fél számegyenessel dolgozol (0, 1, 2, ...) és a bolha valahonnan indulva fölfelé ugrál a számokon)
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Középiskola / Fejtörő
Válaszok
1
TheDevilInMe
{ Vegyész }
válasza
Tegyük fel, hogy az n. idõpillanatban vagyunk és tudjuk, hogy eredetileg hová pottyan a mi kis bolhánk: (i,j). Ezesetben 4 lépésben megtalálhatjuk, ugyanis akkor
- az n. idõpillanatban feltételezve, hogy a bolha É-nak indult az (i,j+n) pontban kell lennie
- az n+1. idõpillanatban feltételezve, hogy a bolha D-nek indult az (i,j-n-1) pontban kell lennie
- az n+2. idõpillanatban feltételezve, hogy a bolha K-nek indult az (i+n+2,j) pontban kell lennie
- az n+3. idõpillanatban feltételezve, hogy a bolha Ny-nak indult az (i-n-3,j) pontban kell lennie
Így a 4 tippbõl valamelyikkel elkapjuk a bolhát.
Ha ezt tudjuk, akkor már csak szisztematikusan be kell járnunk a koordinátarendszert, hiszen akkor elõbb-utóbb a tényleges kiindulási pontra lépünk és akkor 4 lépésen belül elkapjuk a bolhát (a 0. lépésben nyilván nem kell a négy irányt külön vizsgálni). A szisztematikus bejárásra egy módszer a csigavonal, amit mondjuk indíthatunk az origóból.
Ennek megfelelõen az elsõ néhány tipp:
(0,0),
(1,0+1), (1,0-2), (1+3,0), (1-4,0),
(1,1+5), (1,1-6), (1+7,1), (1-8,1),
(0,1+9), (0,1-10), (0+11,1), (0-12,1), ...
Ha becslést akarunk adni a bolha kezdõ pozíciója alapján arra, hogy mennyi idõ alatt kapjuk el (t), akkor a következõt mondhatjuk:
4*(max(i,j)-1)^2-4 < t <= 4*(max(i,j))^2-4
Ugyanis az algoritmus a max(i,j)-1 oldalú belső négyzet minden pontját végigellenõrzi fölöslegesen, az origó kivételével mindet 4 idõegység alatt, viszont a max(i,j) oldalú négyzeten kívüli pontokat biztosan nem kell már ellenõriznie.
- az n. idõpillanatban feltételezve, hogy a bolha É-nak indult az (i,j+n) pontban kell lennie
- az n+1. idõpillanatban feltételezve, hogy a bolha D-nek indult az (i,j-n-1) pontban kell lennie
- az n+2. idõpillanatban feltételezve, hogy a bolha K-nek indult az (i+n+2,j) pontban kell lennie
- az n+3. idõpillanatban feltételezve, hogy a bolha Ny-nak indult az (i-n-3,j) pontban kell lennie
Így a 4 tippbõl valamelyikkel elkapjuk a bolhát.
Ha ezt tudjuk, akkor már csak szisztematikusan be kell járnunk a koordinátarendszert, hiszen akkor elõbb-utóbb a tényleges kiindulási pontra lépünk és akkor 4 lépésen belül elkapjuk a bolhát (a 0. lépésben nyilván nem kell a négy irányt külön vizsgálni). A szisztematikus bejárásra egy módszer a csigavonal, amit mondjuk indíthatunk az origóból.
Ennek megfelelõen az elsõ néhány tipp:
(0,0),
(1,0+1), (1,0-2), (1+3,0), (1-4,0),
(1,1+5), (1,1-6), (1+7,1), (1-8,1),
(0,1+9), (0,1-10), (0+11,1), (0-12,1), ...
Ha becslést akarunk adni a bolha kezdõ pozíciója alapján arra, hogy mennyi idõ alatt kapjuk el (t), akkor a következõt mondhatjuk:
4*(max(i,j)-1)^2-4 < t <= 4*(max(i,j))^2-4
Ugyanis az algoritmus a max(i,j)-1 oldalú belső négyzet minden pontját végigellenõrzi fölöslegesen, az origó kivételével mindet 4 idõegység alatt, viszont a max(i,j) oldalú négyzeten kívüli pontokat biztosan nem kell már ellenõriznie.
Módosítva: 5 éve
0
- Még nem érkezett komment!