|
|
 |
PikkPukk
2013-10-12 00:48:12
|
9074
|
A feladat szöveges része csak annyi volt, amit leírtam. Azért is kérdeztem, hogy kinek mi a véleménye, hogy ki, hogyan értelmezi egyáltalán a feladatot. :D
Ha nem szó szerint értelmezzük, akkor van egyszerűbb megoldás is: pl. az átmeneti bufferes, de igazából még azt is el lehet hagyni.
Sokat nem akarok/akartam foglalkozni a dologgal, az általatok összehozott logika alapján összedobtam egy kódot, hogy lássam működik a gyakorlatban is. (működni látszik)Megnéztem a Wiki-n a moho-t, de én semmi hasonlóságot nem látok a moho és az itt leírt logika között, bár egyáltalán nem vagyok egy elméleti matekos...
(a fórummotornak meg ny..gem) |
|
 |
attoparsec
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. |
|
 |
attoparsec
2013-10-10 20:01:34
|
9071
|
// megjavithatnak mar a forummotort |
|
 |
attoparsec
2013-10-10 19:59:31
|
9070
|
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. |
|
A hozzászólás:
 |
Axióma
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. |
|
Előzmény:
 |
PikkPukk
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. :) |
|
|
Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!
|