Stránka 1 z 1

skuska 27,5

PoslaťNapísal: Str Máj 28, 2008 2:25 pm
od Azteq
chcel by som sa opytat tych co boli na skuske 27,5
ked taky boli, ze co boli za skuskove priklady
ked je to mozne zverejnit

dakujem

Skuska

PoslaťNapísal: Str Máj 28, 2008 5:46 pm
od Cavour
nebol som na skuske, ale nasiel som nieco take:

  Kód:
http://rapasoft.nazory.cz/poznamky/obrazok1.jpg

PoslaťNapísal: Str Máj 28, 2008 7:11 pm
od Dante
takze :D ja som tam aj bol no.. a trebalo to riesit rozdeluj panuj tak to bolo do predu zamyslane... za naivne riesenie bolo C to moje :D ale pravdepodobne sa to da riesit v zlozitosti n cize linearnej a rozdeluj a panuj je pravdepodobne v n log n a moj naivny bol v n na 2 a ten obrazok je moj :P aj tie carbanice 8)

PoslaťNapísal: Str Máj 28, 2008 7:45 pm
od FeroG
Len upresnim, ze riesenie s linearnou zlozitostou je nepravdepodobne (resp. mne a ani kolegom nie je ziadne takeho riesenie zname). Metoda rozdeluj a panuj dava zlozitost O(n.log n). Princip tejto metody je rozdelit si cele pole na 4 rovnake useky (2 useky a-cok a 2 useky b-cok). Potom treba 2. a 3. usek vymenit (linearna zlozitost). Po tejto vymene bude prva polovica pola (prve 2 useky) obsahovat podproblem polovicneho rozsahu. A druha polovica pola tiez predstavuje polovicny problem.

Mozno sa najde niekto, kto bude vediet dat aj dalsie navody na riesenie (mozno na internete sa nieco najde :) ...).