Keresés

Részletes keresés

Sirpi Creative Commons License 2013-10-09 18:51:46 9065

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.

 

A hozzászólá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?

Előzmény:
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!