Keresés

Részletes keresés

Axióma Creative Commons License 2013-10-10 20:49:13 9073

Szuper. [Nem ugy mint a forummotor, szerintem ismet jopar honap mire meggyogyitjak...]

Igazabol mivel majdnem fuggetlen az egymas utani valasztas, csak arra nem jottem ra, hogy hogyan lehet jol megfogalmazni (elindultam forditva, hogy a doboz + kovetkezoben mind a 26 betu szerepel, de ebbol nem jon ki me'g).

A hozzászólás:
attoparsec Creative Commons License 2013-10-10 20:03:31 9072

moho = optimalis.

 

a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.

legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).

legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.

ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.

a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.

indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].

az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.

 

 

// bocs, ha ez esetleg duplan jelenne meg. majd kitoroltetem a modikkal.

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

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