Keresés

Részletes keresés

Axióma Creative Commons License 2013-10-09 15:42:44 9064

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?

Axióma Creative Commons License 2013-10-09 15:40:27 9063

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).

A hozzászólás:
PikkPukk Creative Commons License 2013-10-09 14:21:20 9062

Sziasztok!

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?

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!