Keresés

Részletes keresés

Axióma Creative Commons License 2013-10-10 19:09:51 9069

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.

A hozzászólá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. :)

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

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