Na akkor legyen egy feladat is...infósoknak...bocs.:-)
*** Van egy fájlod, melyben változó hosszúságú rekordok vannak. A rekord-elválasztó ismert, pl. legyenek benne null-terminált stringek.
Feladat: ki kell választani véletlenszerűen egyet a rekordok közül, úgy hogy mindegyiknek azonos legyen az esélye.
Megszorítások: Csak akkora memóriát használhatsz amelybe garantáltan belefér bármelyik rekord, de több nem, plusz még konstans méretűt. Vagyis adott a max rekordméret (pl. N), a használható memcsi: N+O(1) Remélem elég precíz voltam :)
Ja, lehetőleg optimális megoldásokkal bombázzatok... :))))
(A filéből való olvasás nagyon-nagyon drága művelet)
Természetesen ti nyertetek. Mentségemre legyen mondva: már régóta sejtettem, hogy egy munkahelyen képtelenség gondolkodni. Mihelyst beültem az autóba belém hasított a felismerés, csak már lusta voltam visszamenni és beírni.
Még szerencs, hogy időben abbahagytam a matek szakot és maradtam informatikus.
Udv N e t S h a r k,
Mi lenne ha a láncolt listárol készitenénk egy másolat listát. Mondjuk egy rendezettet. Az első elem amelyet nem tudunk felfűzni, ott a hurok.
iu.: Remélem a lista csak egymástól eltérő elemeket tartalmazhat. (Halmaz)
(Most vagyok először az Asztalnál, de ez a topic nagyon rulez, úgyhogy gyorsan regisztráltattam magam, remélem nem bánjátok.)
N e t S h a r k:
Nagyon király ez a láncolt listás feladat. Furcsa, de valamire nagyon emlékeztet, de nem tudok rájönni mire (valami tétel bizonyítás ? nemtom...), ilyen formában viszont még nem találkoztam vele.
IMHO a megoldás: Tfh. minden listaelemnek van egy sorszáma, amely egy pozitív egész szám. Ezenkívül ne legyen "kihagyás", azaz ha pl. N elem van, akkor 1-től N-ig minden szám legyen kiosztva sorszámnak.
Ezután sétálgassunk szépen a listában, és jegyezzük meg, hogy hány elemet láttunk, és hogy mi volt a látott sorszámok maximuma.
Namármost, ha bármikor a látott elemek száma nagyobb, mint a sorszámmaximum(sic!), akkor van hurok, egyébként nincs (ha tényleg végtelen a lista, akkor utóbbi esetben sose lesz vége, vagyis ez egy parciálisan eldönthető probléma) a hurkolódás helyét viszont sajna nem tudjuk megmondani.
Erre gondoltál?
Az is igaz viszont, hogy szigorúan véve ehhez nem konstans, hanem N-től függő nagyságú memcsi kell, ha jól érzem, akkor O(log(N)), a szokásos architektúrákon.
Mivel az előző megjegyzésed szerint semmi információt nem tudsz megjegyezeni, azt jelenti hogy az egész algoritmusod semmi előző információval nem dolgozhat (nincs memória), vagyis az adott beolvasott rekordból kellene tudni eldönteni, ami ugye csak olvasható, hurokra vonatkozó információt nem tartalmaz...
Szóval adott a következő probléma:
Tegyük fel mégis megjegyzel mondjuk minden rekordról M méretnyi infót.
Memóriád mérete N. Ha van egy hurkod ami hosszabb mint int(N/M)+1 azt hogy oldja meg az algoritmusod?
Felejtsétek el azt a szót, hogy végtelen. Egy számítógépnek egy lista már akkor is végtelen, ha nem fér be a memóriájába. Itt most erről van szó. A rekordokról pedig valóban semmi infót nem tudsz megjegyezni.
Az a baj, hogy nekem is mennem kéne már. Szerintem eleg jol leirtam az eredeti kiirasomban. Annyit tennek hozza, hogy a lista tagjaiba nem tudsz beleirni, de felesleges is lenne, hiszen ugysem tudnad tarolni a modositott listatagokat, hiszen limitalt a memoriad. Mondjuk, hogy a listat egy gep adja neked, amitol le tudod kerdezni a kovetkezo elemet és slussz.
Jujj, hamu a fejemre szor, szor. Na en ugyi arra nem gondoltam, hogy jajj, na nem is reszletezem.
Hmm. Viszont az a bibi, hogy barmi ilyen atlos-modszer, meg hasonlok meg tarkapcitast igenyelnenek. Hmm. Mar le se irom, mert azzal is a baj, hogy a listameretehez kepest kovetel valamekkor tarkapacitit.
De telleg, akkor ird mar le nagyon konkretan, hogy mik az osszes megszoritasok? (addig is agyalok, de mar megint el kell rohanni :-()
Van két kancsóm, egyikben egy liter bor, másikban 1 liter víz. ... Kérdés, hogy a vízben lesz több bor, vagy a borban lesz több víz? heh-heh-heh, természetesen a borban lesz több víz, ugyanis a bornak már eredetileg van igen magas víztartalma ..
:->>
Ha végtelen a lista és ezért semmilyen jellemzoje nem tartható a rekordokról memóriában vagy egyéb tárolón, akkor ez egy baromság hiszen a hurok is lehet tetszolegesen távoli elemek közt, ami természetesen tetszolege puffer méretet túlnohet. Mármint a hurokban szereplo rekordok valamilyen azonosítója.
Szóval öreg Turing tekeredik a sírjában vagy épp gombot készül varrni erre...
Hmmmmm.
Jajjajjjaj. Megegyszer es utoljara megprobalom elmondani, hogy miert nem jo a megoldasod. Veszed az elso elemet. Megjegyzed. Fasza. Az mutat a masodikra. A masodik a harmadikra, .... a kilencedik a tizedikre. A tizedik pedig a masodikra (itt a hurok), a masodik a harmadikra.... Hiaba jegyezted meg az elsot, oda soha nem jutsz vissza es nem veszed eszre az utana levo hurkot. Arra mar sor sem kerul, hogy a masodikat megjegyezve onnan is elindulj, mert ott bolyngasz a masodik es a tizedik kozott. Telleh nem ertem, hogy miert kell ezt ennyit magyaraznom. De ugyis megmagyarazom valahogy, ha torik, ha szakad. :)
Azt irtad, hogy a "vegtelensegig" lepegetek. Pedig ha a lista veges, akkor nem, hanem csak a vegeig lepegetek. Aztan jon a kovetkezo elem, azt is hasonloan csekkelem, hogy nem alkot-e hurkot. Ha a lista veges, elobb-utobb vegzek vele, csak mint emlitettem kicsit kurva hosszu az algortimus, tekintve, hogy negyzetesen no a lista elemeinek szamaval.
ebben en is ezt javasoltam. Most akkor csak nem vetted eszre, hogy nyitott kaput dongetsz? A masik lehetoseg, hogy ket ladikban oroljuk a malmot, vagy mi :-)
Na ne értetlenkedj!
Ugye a paritás számolást (informatikusok kedvéért) a következo analógiával értjük.
Legyen mondjuk a fekete 0, a fehér 1 (ez az informatikus választás : ég a lámpa, vagy nem ). Ezután a válasz : szumma az általam látott sapkáknak megfelelo értékeket majd mod(2).
Ugye ez azt jelenti hogy a fehér sapik paritását nézzük. Szóval ugyanígy lehetne ez akár a fekete is (mondjuk a beduinoknál délben). Na ezt hívom paraméternek, s ha nem vagyok informatikus, de mindenki okos a játékban s ezt az algoritmust következteti ki (tf. valóban ez a legegyszerubb) akkor arra is rájövök hogy ezt a paramétert meg kell határozni... (Mondj olyan okfejtést ami ezt cáfolja!)
Ezután a feladat, azt megmondani, hogy választ algoritmust a "nép"?
