A feladat szöveges része csak annyi volt, amit leírtam. Azért is kérdeztem, hogy kinek mi a véleménye, hogy ki, hogyan értelmezi egyáltalán a feladatot. :D
Ha nem szó szerint értelmezzük, akkor van egyszerűbb megoldás is: pl. az átmeneti bufferes, de igazából még azt is el lehet hagyni.
Sokat nem akarok/akartam foglalkozni a dologgal, az általatok összehozott logika alapján összedobtam egy kódot, hogy lássam működik a gyakorlatban is. (működni látszik)Megnéztem a Wiki-n a moho-t, de én semmi hasonlóságot nem látok a moho és az itt leírt logika között, bár egyáltalán nem vagyok egy elméleti matekos...
Szuper. [Nem ugy mint a forummotor, szerintem ismet jopar honap mire meggyogyitjak...]
Igazabol mivel majdnem fuggetlen az egymas utani valasztas, csak arra nem jottem ra, hogy hogyan lehet jol megfogalmazni (elindultam forditva, hogy a doboz + kovetkezoben mind a 26 betu szerepel, de ebbol nem jon ki me'g).
a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.
legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).
legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.
ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.
a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.
indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].
az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.
// bocs, ha ez esetleg duplan jelenne meg. majd kitoroltetem a modikkal.
a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.
legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).
legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.
ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.
a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.
indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].
az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.
Ugyan mar, nem a koszonet miatt kerdeztem vissza, hanem mert azt remeltem, hogy tovabbi dolgok is kiderulnek a feladatrol. Mert a moho = optimalis bizonyitasa nem mozgatta meg senki fantaziajat, es ladapakolaskent is lehetne rajta csemegezni attol fuggoen, hogy mit tudunk az inputrol.
Hat ezt nem ertettem az elobb sem, hogy miert nem ugyanaz? HA elore nezheted az inputot, akkor nem mindegy, hogy az elejen megnezed, addig nem rakod sehova, majd kivalasztod a dobozt, es belerakod az addigi betuket, vagy azt mondod, hogy most rakod mar egy dobozba, ami egy betus, de a vegen mondod meg, melyik betu volt az? Ha jol ertem, a minimalizalasi feladatnak inputja a hosszu string amit be kell tenni, az outputja absztrakt ertelemben a minimum valtasok szama, de gyakorlatban sokkal jobb azt mondani, hogy egy rovid string, ami azt mutatja, hogy melyik dobozokat hasznalod (es mindig akkor valtasz, amikor a doboz jelevel egyezo betuhoz jutsz); es persze aminel nincs rovidebb megfelelo string. [Az sztem veheto trivialisnak, hogy ha a rovid string minimalis hosszu, akkor tok mind1, hogy hogyan volt a valtasok hatara eredetileg, a fenti "akkor valtok amikor muszaj" algoritmus ugyanugy alkalmas lesz, csak a valtasok koruli invarians - egyikbe se tartozo - betuket csoportositja mashova.]
En nem latok kulonbseget a ket interpretacio kozott. Azt viszont nem latom me'g egzakt modon bizonyitottnak, hogy a moho algoritmus az egyuttal mindig minimalis lesz. Erzesre igen, de ennek a matematikai kerdese szerintem ez lenne.
Ahogy olvasom, utólag akarod felcimkézni a dobozokat, pedig előre rá vannak írva a betűk a feladat szerint. Az alapján viszont azt a betűt kéne választani, amelyikből az első példány legutolsóként fordul elő. Ezután dobozváltás, és a következőnek megint azt a betűt kell választani, amelyikből az innentőli első előfordulás utolsóként fordul elő stb. Érzésre ez az optimális. Ennek eldöntésére pedig nem jó egy 26 bites számot használni? Elindulunk a betűkön sorba, és minden talált betűhöz tartozó bitet 1-re állítunk. Amikor a számunk minden bitje 1-essé válik, megvan, melyik dobozzal kell kezdeni.
Ujraolvasva a hsz-od veget, mi a baj a cimke nelkuli dobozzal? Az elvi szinten nincs, ha barhova beleolvashatsz az inputba, vagy tenyleg a feladatot nem ugy ertem, ahogy irod.
Mindig elore kene eldonteni az input ismerete nelkul, hogy melyikbe rakod, kvazi ladapakolasi algoritmus-szeru dolgot kene keresni?
Eloszor azt hittem, ez a KMP mintaillesztesi algoritmus elofeldolgozasahoz lesz hasonlo, de nem tunik ugy, sztem az egyetlen kerdes, hogy a moho algoritmus jo-e a feladat megoldasahoz. Mohonak itt azt hivom, hogy mindegyik pozicioban az elozoleg hasznalt dobozt hasznaljuk mindaddig, amig van legalabb egy betu ami me'g nem volt benne; es amikor az utolsot is elhasznalnank, akkor a regi dobozt lezarjuk es megcimkezzuk azzal, es az uj dobozba pakoljuk az aktualisat meg onnan a tobbit. (A vegen az utolsora barmely lehetseges cimket raragasztod). Ehhez csak 26 bitet kell allitgatnod, uj doboznal inicializalas es szamlalo allitas, uj betunel kihuz vagy sem, semmi extra algo.
Kerdes, hogy betlizhet-e a moho? Elsore azt mondanam, hogy nem hiszem, de most nem allnek neki bizonyitgatni. Az trivialisan kijon belole, hogy a szoveg hossza per 25 a worst case csereigeny (-1 ha az elso nem szamit cserenek).
Elkezdtem én is ilyen logikai feladatokkal foglalkozni. Van jó pár amit én is ki tudok találni, vagy ha nem akkor kigúglizható, de erre sehol nem találtam válasz. Ez alapvetően egy programozási kérdés, és programozási megoldást tudok is rá néhányat, csak az a kérdés, hogy esetleg van-e rá jó logikai megoldás is?
Van 26 dobozunk az angol abc egy-egy betűjével ellátva. A dobozokba betűket lehet rakni, kivéve az adott dobozon szereplőt. A kérdés az, hogy minimum hány dobozváltás szükséges, hogy az összes betűt behelyezzük a dobozokba egy adott karaktersorozatra.
- Egy dobozba akármennyi betűt belerakhatunk egymás után is és egy dobozt akárhányszor használhatunk újra.
- Dobozváltás alatt azt értjük, hogy ha az adott ponton egy másik dobozba kezdjük rakosgatni a betűket.
- A sorozat bármilyen hosszú lehet, egy karakter természetesen többször is előfordulhat.
Milyen algoritmussal lehetne az optimális (tehát minimális dobozváltásos) megoldást megtalálni?
Milyen adatszerkezettel lehetne ezt hatékonyan?
Könnyítés lehet az, hogy az input string-hez bármilyen sorrenben hozzáférünk, de a dobozokba az eredeti sorrenben kell, hogy kerüljenek a betűk.
Szóval hogy lehet ezt a feladatot megoldani annélkül, hogy plusz buffert (egy címke nélküli üres dobozt) használnék?
Én is megoldottam, trükk nélkül. Három gyufaszálat helyeztem át más helyre. Viszont nekem a jelek közötti szabad helyekkel és az esztétikai szempontokkal van gondom...
Nem igazan ertem ra eddig komolyabban foglalkozni vele, csak raneztem, annyibol me'g nem trivialis. De majd ha kialszom magam rendesen, kivancsi vagyok, hogy megoldom-e... programot tuti nem irok most, annyi idom nincs.
Azt hiszem az a lényeg, hogy arab számokat használ, és nem keveri római vagy egyéb számokkal. Az arab számok egyik lehetséges megjelenítési formája a digitális számjegy, amiket pálcikákkal meg lehet jeleníteni, és mivel mindenk ismeri ezt a jelrendszert, ezért ezt használja, és amíg egyértelmű, hogy milyen számjegyekről van szó, addig megfelelő. Neked sikerült megoldani?
Nem tisztem magyarázni, de azt hiszem elsiklottál pár dolog fölött. Egyrészt a többnyire szót nem vetted észre a mondatban. Másrészt sokféle számológép kijelző létezik.
Nem tudom, hogy te vagy-e a rejtveny kozzetevoje, de eleg erdekes a hosszu bevezeto utan, hogy mar az elso rejtveny nem felel meg a sajat leirasanak. Nevezetesen az elejen azt allitja, hogy a rejtvenyek megjelenesi formaja a szamologepeken szokasos, kulon kiter az egyes szamjegyek kozotti helyekre, illegalisnak ertekelve a csusztatasokat, erre a peldaban az 1-es szamjegyet ugy rajzolta fel, hogy egy fel helyen van.
Egyebkent meg ehhez a rejtvenytipushoz egyszer kell felepiteni egy adatbazist, az N darab gyufaszalbol ervenyes egyenlosegek halmazat, utana mar csak a "tavolsagot" kell nezni. Aki algoritmusok tantargyat tanit, feladhatna' mint backtrack keresesi feladat:)
azt nem vettem észre, hogy nem kell "optimálisnak" lennie a módszernek, azaz nem az első lehetséges alkalommal kell szólni, hanem ráér valamikor később is, amikor már tuti a dolog
Kimész a 4. napon, ég a lámpa, mert előtted már voltak kint, az első meggyújtotta, a többi nem bántotta, te eloltod. Kimész a 15. napon, megint ég a lámpa, tehát volt kint valaki más is, mint aki először meggyújtotta, mert ő már többször nem gyújthatja meg, eloltod, és tudod, hogy két különböző ember már járt kint. Kimész a 32. napon, nem ég a lámpa, tehát közben csak az első két ember volt kint, akik már nem gyújthatják meg. Ahányszor égve találod, eloltod, és tudod, hogy egy-egy új ember is kint járt. A kilencediknél biztos lehetsz benne, hogy ha nem vertek át, akkor mindenki járt már kint.
Szerintem nem ezt jelenti a feladat... hanem azt, hogy ha mondjuk én vagyok az az adott ember, akinek ezt tudnia kell, akkor amikor alkalmanként pont rám kerül a sor, akkor meg kell tudnom mondani, hogy volt-e már mindenki vagy még nem. De lehet, hogy én értem félre.
Tehát mondjuk kimegyek a 4. napon, ekkor nyilván még nem, aztán kimegyek mondjuk a 15-en, még ekkor sem, aztán a 32-en, na ekkor már igen... vagy valami ilyesmi.
Jelölj ki egy lámpaoltogatót, a többinek meg mondd meg, hogy egyszer meggyújthatja a villanyt, ha éppen nem ég, amikor bemegy a mosdóba. A lámpaoltogató meg csak számlálja, hogy hányszor kellett eloltania a lámpát. A kilencediknél kiabáljon az őrnek.
Valaki segítene megoldani ezt a feladatot? Van 10 ember, akiket egyesével bezárunk egy szobába. Naponta kiengedünk közülük egyet a mosdóba, majd vissza kell mennie. Majd másnap megint kiengedünk valakit, azonban a kiválasztás véletlenszerűen működik, tehát ha valaki volt már kint, attól még ugyanolyan eséllyel mehet ki újra. A mosdóban a villanyt szabadon fel ill. lekapcsolhatják, ez az egyetlen jel, amivel kommunikálhatnak egymás között. A feladat lényege egy olyan módszer kidolgozása a kommunikációra a villanykapcsolón keresztül, amivel egy adott bemenő ember tudja, hogy rajta kívül mindenki volt-e már bent.