Keresés

Részletes keresés

PikkPukk Creative Commons License 2013-10-10 13:18:31 9068

A feladatban előre felcímkézett dobozok vannak, ezért kellett Sirpi módosítása is, bár az alapötlet a tiéd volt. Köszi neked is. :)

A hozzászólás:
Axióma Creative Commons License 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.

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

 

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