Amikor Arszlán elmesélte a többieknek a múltkori fogdás feladványát, Beliánnak eszébe jutott erről egy másik trükkös feladat.
– Képzeljétek el, egyszer mikor épp hosszabb szabadságomat töltöttem bent a hűvösön, az egyik foglár fura feladatot adott nekem. Bevitt egy szobába, ahol egy hatalmas kupacban nagyszemű, nehéz lánc volt feltornyozva. De tényleg rengeteg volt ott, több tonna is lehetett. – kezdte Belián.
– Azután közölte, hogy az egész kupac igazából egy hosszú lánc. A kezembe is adta az egyik végét. A feladatom az volt, hogy megállapítsam, vajon véget ér-e valahol a lánc, vagy pedig önmagába visszacsatlakozik valahol.
– De hát ez könnyű, csak végig kell nézni és ha van elágazás benne, akkor tudod, hogy körbeér valahol! – szólt közbe izgatottan Cipórián.
– Sajnos ez nem ilyen egyszerű. – ingatta a fejét Belián. – Megtévesztésül ugyanis időről-időre beiktattak egy-egy elágazást a láncba. Persze a haladási irány meg volt jelölve, szóval nem volt kérdés, hogy merre megy tovább a lánc. De sose tudhattam, hogy éppen a lánc önmagába visszatérő hurkát látom, vagy csak egy vakvágányt.
– És nem tudtad volna egyszerűen a szoba másik végébe átpakolni az egészet az elejéről kezdve? – vettette közbe Arszlán.
– Á, borzasztó nehéz volt a lánc és nagyon hosszú is. Elárasztotta az egész szobát, nem tudtam volna rendesen elválasztani, hogy mi az amit már láttam és mi az amit nem. – ábrándította ki Belián. – Arra is gyorsan rájöttem, hogy ha egyszerűen csak az elejéről elindulva követem a láncot, akkor ítéletnapig is ott lehetek, ha tényleg kör van benne.
– Végül a két cipőfűzőmből csináltam két jelölőt, és mire visszatért a foglár, már tudtam a választ, így jutalmul aznap este fejedelmien megvacsorázhattam. Mondhatom igen jól esett!
Vajon hogy csinálta?
Update: A zsákutcákban is lehetnek kereszteződések, melyek úgy vannak jelölve, mintha a főágba csatlakoznának vissza. Sőt akár ténylegesen vissza is térhetnek a főágba egy másik zsákutca felől csatlakozva. Ettől független, hogy a főágon végülis van-e kör vagy nincs.
A feladat – legalábbis szándékaink szerint 🙂 – izomorf a következővel: egy egyirányú láncolt listában állapítsuk meg, hogy van-e kör, konstans tár- és a lista hosszában lineáris időbonyolultság mellett. Shadowrunner megoldása volt az, amit kerestünk, vagyis hogy két különböző sebességgel mozgó mutatóval (cipőfűzővel) haladunk végig a listán (láncon) és a gyorsabb vagy a lista végére ér, ekkor nincs kör, vagy pedig utoléri lassabbat, ekkor pedig van kör.
A feladat kissé zavaros bemutatásáért utólag is elnézést kérünk, hamut szórunk a fejünkre stb. Egyéni keretemből felajánlok egy éves Fogaskerék előfizetést annak aki egy jobb, érthetőbb fizikai analógiát ad erre a feladatra.
Comments are closed.
Én egy ilyen algoritmus követnék:
1. elindulok a végétől. Itt két eset lehet:
2. elérek egy elágazáshoz. Megjelölöm a jó irányt és elindulok a másik irányban.
2.a: eljutok egy elágazáshoz, aminél egyik ág sincs megjelölve: ez az ág zsákutca, -> felveszem a jelölőt és megyek az 1.pontra
2.b: elérek az ág végére: ez az ág zsákutca -> felveszem a jelölőt és megyek az 1.pontra
2.c: elérek a jelölőik: kör van a láncon
2.d: eljutok egy elágazáshoz, aminél meg van jelölve az egyik irány: kör van a láncon
3. a lánc végére érek: nincs kör a láncon
Így elég egy jelölő, mert azzal egyértelműen jelölhető a követendő ágat egy zsákutca után.
@Shadowrunner: Érdekes, Belián szerint az előző delikvens pont így oldotta meg a feladatot.
Ezért nehezítettek rajta annyit, hogy a zsákutcákban is raktak kamu kereszteződéseket, és úgy jelölték meg őket, mintha a főágba csatlakoznának be. Akár az is lehet, hogy két zsákutca össze van kötve és vissza lehet kavarodni belőle a fővonalra attól függetlenül, hogy a fővonalon végülis van-e kör vagy sem.
Így a 2a illetve 2d pontod sajnos nem működik.
🙂
@-Maya: ha két zsákutca össze van kötve, akkor van hurok (kör) a láncon. vagy nem?
hová tűnt, amit írtam?
haszóval, ha két zsákutca össze van kötve, akkor van hurok a láncon. vagy mégsem?
na, az egyik fölösleges.
@EÖ: Valami van a bloggépel, mert az előző hosszászólásod látszott RSS-ben, meg pl. Encsé gépén is, de nálam nem. Aztán most megjött mind a kettő. Mágia.
Na a témához visszatérve, csak az a kör számít ami a fővonalon van. Ettől függetlenül a mellékágakon úgy össze lehet gubancolva a lánc, ahogy tetszik.
Csak hogy világos legyen: egy egyirányú láncolt listát próbáltunk megvalósítani ezzel a lánc dologgal. De érezzük, hogy kicsit erőltetett lett… Egy másik példa lehetne egy olyan úthálózat, ahol minden kereszteződésben van egy kötelező útirány (három behajtani tilos + egy amerre menni lehet). Nem tudom, hogy ez így érthetőbb lenne-e.
Szerintem igen…
@-Maya: matematikailag nincs fővonal egy csomón (lánc)
szerintem.
hiszen átalakíthatók egymásba
@encse: szerintem nem.
Nekem a legjobban az a változat tetszett, amikor hőseink egy furcsa Escher-labirintusba érkeznek, ahonnan az elágazásokban mindig csak lefelé vezet az út, de néha feljebb kötnek ki, mint ahonnan elindultak. Az a kérdés, hogy az ilyeneket hogy lehet detektálni. Persze ez is erőltetett, a legjobb a láncolt lista. De megajánlok egy gumi fogaskereket annak is, aki értelmes gyakorlati alkalmazást ad rá… 🙂
@EÖ: Minden elágazásnál egyértelműen meg van jelölve, hogy merre kell továbbmenni, ezt hívom én főiránynak, fővonalnak, stb. Ez nem minden láncnak van, hanem egy speciális tulajdonsága a szóbanforgó láncnak. A kérdés, hogy ezt az útvonalat követve körbeérünk-e valahol, vagy sem.
@-Maya: Nekem még nem teljesen világos dolog. Azért örlülök, hogy az első verziót sikerült megoldani 🙂
Mi a fővonal definíciója, illetve hogy van jelölve?
Azaz hogy kell érteni, hogy a mellékágakban is úgy van jelölve a kereszteződés, mintha a főágba menne vissza? Mert ha ez ténylegesen nem igaz, akkor a jelölések sem igazak, így félrevezetőek, nem lehet megbízni bennük.
Vagy az van, hogy a mellékvonalakról lépkedve nem lehet eldönteni, hogy a kereszteződés az mibe fut bele?
Az egyirányú láncolt listára csak annyiban nem hasonlít, hogy ott a tényleges visszacsatolást előre lépkedés közben nem lehetne látni, azaz bármilyen elágazás az csak kifelé menő lehet, befelé jövő nem.
Az úthálózatos probléma meg valahol a kettő között van, mert ott látod a becsatlakozó oldalágakat, de nem mehetsz be rajtuk.
De így a 3 esetből (láncos, utas, láncolt listás) nekem egy ilyen feladat körvonalazódik:
úgy kell megállapítani egy fővonalról, hogy körmentes-e, hogy a visszacsatolásokat látod ugyan, de nem mehetsz be rájuk és nem látszik rajtuk, hogy az vakvágány, vagy visszacsatolás.
@Shadowrunner: A láncnál is az lenne a lényeg, hogy reménytelen legyen a leágazásokat vizsgálni.
Mégegyszer: a láncon minden elágazásnál az egyik ág egyértelműen meg van jelölve, mint haladási irány. Ez igaz a vakvágányokon/oldalágakon is. A kérdés, hogy a megadott kiindulási pontból, a haladási irányt követve van-e kör a láncban.
@-Maya: na de akkor miért van elágazás, ha úgyse mész rá, mert jelölve van
Ugyanis:
Az egyik vége ismert, onnan indulunk. rákötjük a madzagunkat aztán megyünk, és az elágazásoknál, mivel meg van jelölve a haladási irány így mindig a főágon megyünk tovább, hiszen a többi nem érdekes. Két eset lehetséges:
Visszajutunk a madzagunkhoz, azaz a láncon a főágban hurok van.
Egyszer csak vége szakad a láncnak, mert megvan a másik vége, azaz a láncon a főágban nincs hurok.
@EÖ: Az elágazás azért kell, hogy lehessen látni, hogy hol köthet be esetlegesen a visszatérő hurok.
Ha csak a végén lenne egy jelölő, akkor abba nem biztos, hogy belefutunk, még ha kör is van a láncon. Ugyanis a láncban lehet egy hosszú, bevezető szakasz, ami még nem a kör része.
Így az alábbi módszer kell:
Egy lépésnek azt tekintem, hogy a következő elágazásig megyek.
Az első jelölővel mindig 1-et a másodikkal mindig 2-t lépünk előre, felváltva. Ha a második mozgatása során keresztezem az elsőt, akkor kör van. Ha a lánc végére érek, akkor meg nincs kör.
Ez azért jó, mert az első jelökő is folyamatosan mozog előre, így előbb utóbb rajta lesz a körön. A két jelölő közötti növekvő távolság meg azt garantálja, hogy ha rajta van mind a kettő a körön, akkor előbb utóbb keresztezem a 1. jelölőt.
Azaz, ha a jelölők közötti távolság nagyobb mint a kör hossza és az első jelölő rajta van a körön, akkor a 2.tól elindulva a távolságot legyalogolva elérem az 1.-t.
@Shadowrunner: na de ha a hurok csakis a fővonalon lehet és te csakis a fővonalon haladsz (mert tudod melyik az, a feladat kiírása szerint) akkor is visszakerülsz az elejére, tökmindegy milyen hosszú bevezető szakasz van a hurok előtt.
@EÖ: Bocs, ez lehet, hogy félreérthető volt, csak az elágazásoknál van megjelölve, hogy merre vezet tovább az út.
Ránézve a láncra egy véletlenszerű ponton nem dönthető el, hogy az része-e a fővonalnak. Ez utóbbit úgy definiáljuk, hogy a láncnak az a része, melyet a megadott kiindulási pontból a kereszteződésekben a kijelölt haladási irányt követve elérhetünk. Pl. egy másik kiindulási pontot véve egész más lehet a fővonal.
Ha sok időm lesz, egyszer megírom ezt a feladatot labirintussal is. Mondjuk olyan [blue]House[/blue] of Leaves stílusban. 😉
@EÖ: a hurok a fővonalon van, de az nincs kikötve, hogy a hurok az elejére köt vissza. Azaz pl lehet a fővonal P alakú, ahol a P lábától indulsz el. Ha a lábához teszed a jelölőt, akkor oda nem fogsz tudni visszaérni, mert a huroknál a P “hasán” fogsz körbe körbe járni.
@Shadowrunner: úgyvan. a P-elágazásnál nem fordul meg az irány. nálad a pont.
Csak hogy jól értem -e a feladatot:
Egy irányított gráfról is lehetne szó, ahol minden csúcsból pontosan egy él vezet ‘kifelé’. (elágazásnál ‘visszamenő’ éleket csak cipőfűző segítségével tudunk megkülönböztetni) Ebben kellene egy kezdőpontból indulva végpontot találni vagy kört detektálni két jelölővel úgy, hogy a méretét sem ismerjük.
Esetleg kihagytam valamit?
@csakazertse: Végpontból persze nem vezet ki él, de egyébként stimmel szerintem.
Én ebbe a feladatba most nem vágtam bele (időhiány), de elég erőltetettnek tűnik nekem már csak annak alapján is, hogy 20 komment csak az értelmezésével foglalkozik.
Tudom, adjak jobb feladatot, ha tudok 🙂
Majd talán egyszer ha ihletem és időm lesz.
@Szajmong: Jogos a kritika, bár azért születtek itt megoldások is 🙂