|
|
 |
Axióma
2013-10-09 20:02:41
|
9067
|
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. |
|
 |
PikkPukk
2013-10-09 19:54:58
|
9066
|
Ok, ez már elég jó logika.
A feladat az (gondolom), hogy a dobozváltások számát a minimálisra csökkentsük, erre ez tökéletesen megfelel.
Már csak 1-2 számláló kell, hogy mettől meddig tart az a blokk, amit a kiválasztott dobozba rakunk.
Köszi a segítséget. :) |
|
A hozzászólás:
 |
Sirpi
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.
|
|
Előzmény:
 |
Axióma
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? |
|
|
Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!
|