Stránka 1 z 1

uloha 213

PoslaťNapísal: Ned Jún 17, 2012 9:49 pm
od dzusik12
z hentej zbierky priklad http://brodenec.ic.cz/ta2/uu.pdf

213. O súčte x 22
Daná je postupnos» n celých (kladných i záporných) èísiel. Nájdite v nej podpostupnos»
(ľubovoµnej då¾ky  n) po sebe nasledujúcich èlenov postupnosti s najväčším súčtom.
Dobre po¹pekulujte nad najlep¹ím a najrýchlej¹ím rie¹ením. Problém je ťažší, než sa
na prvý pohľad zdá.

je tam riešenie v čase o(n na 3) že skúšať všetky možnosti,
potom je naznačené riešenie v čase o(n na 2) vypĺnanie tabuľky by som to nazval, resp dynamicke programovanie - to zvládam, a potom je spomenute že metoda rozdeluj a panuj že rozdeliť na dve časti a spojiť a vybrať najvačšiu z prvej časti z druhej a z prostrednej
skúšal som si to nakresliť jak by som to rozdelil a vyberal, ale neviem si predstaviť to pravidlo spájania, viete mi nejako poradiť ?
to je riešenie v čase o(n logn)
to riešenie v čase o(n ) chapem

Re: uloha 213

PoslaťNapísal: Ned Jún 17, 2012 11:05 pm
od Aries
Linearne riesenie je pomerne jednoduche, snad mi nic neuniklo.

Kod by vyzeral nejak takto:

  Kód:
riesenie = 0 //riesenie pre prazdnu podpostupnost je rovne nula, skusime najst lepsie
aktualne_riesenie = 0 //najlepsie riesenie konciace v aktualnom prvku pri prechadzani postupnosti
for cislo in postupnost:
   aktualne_riesenie = max(0,aktualne_riesenie+cislo)
   riesenie = max(riesenie,aktualne_riesenie)


Preco to funguje? (aspon dufam :))
Vezmime si situaciu v nejakom prvku i. Mame dve moznosti - zahodit i-ty prvok a zacat novu podpostupnost nasledujucim prvkom. Druha moznost je sucasny prvok vziat a pridat ho k nejakej podpostupnosti konciacej predoslym prvkom (alebo v trivialnom pripade zacneme novu postupnost). Nemusi nas zaujimat cim zacala, hladame len najlepsi sucet (to je pre aktualne skumanu podpostupnost ulozene v premennej aktualne_riesenie).

Predpokladajme, ze priebezne riesenie pre podpostupnost konciacu predoslym prvkom mame najdene.
Kedy sucansy prvok zahodit? Pokial je kladny, asi to nema zmysel robit, ved nam zvysi skore. Ak bude zaporny, pozrieme sa co spravi jeho pridanie:
- ak nam jeho pridanie sposobi, ze aktualny sucet bude zaporny, nechceme ho. Mozme predsa v dalsom zacat novu podspostupnost a sucet bude teda nula, nebudeme si ho teda znizovat tym, ze budeme mat podpostupnost so zapornym suctom.
- ak bude po pridani sucet stale kladny, skusime ist dalej.

Nasledne bude riesenim maximalna hodnota, ktoru sme pri takomto prejdeni postupnosti nasli.

Snad to je aspon trochu pochopitelne, to moje vysvetlenie nie je prave najkrajsie.

Formalne dokazat by sa to snad dalo napriklad indukciou, co prenechame citatelovi (lebo sa mi to nechce :P).

Re: uloha 213

PoslaťNapísal: Ned Jún 17, 2012 11:39 pm
od dzusik12
ale praveze linearne riesenie chapem, ale to n log n sa pytam ze jak

Re: uloha 213

PoslaťNapísal: Pon Jún 18, 2012 12:01 am
od Aries
Aha, ja uz v poslednom case neviem ani citat :)

Re: uloha 213

PoslaťNapísal: Uto Jún 19, 2012 9:47 am
od dzusik12
taze nevie nikto jak to zriesit cez rozdeluj a panuj ?

Re: uloha 213

PoslaťNapísal: Uto Jún 19, 2012 2:30 pm
od johny
dzusik12 píše:taze nevie nikto jak to zriesit cez rozdeluj a panuj ?

Časť "rozdeľuj" je snáď zjavná. Máme teda nasledujúcu situáciu:

(1) poznáme postupnosť s maximálnym súčtom z ľavej polovice [l, c)
(2) poznáme postupnosť s maximálnym súčtom z pravej polovice [c, r)
(3) potrebujeme nájsť postupnosť s maximálnym súčtom z celého intervalu [l, r)

Výsledkom bude buď postupnosť z (1) alebo postupnosť z (2), alebo iná postupnosť, ktorá sa ale nesmie nachádzať celá v ľavej ani celá v pravej polovici (inak by sme ju boli našli v (1) alebo (2)). Teda musíme len nájsť postupnosť s maximálnym súčtom prechádzajúcu stredom intervalu c. Môžeme si ju rozdeliť na dve časti -- ľavú [a, c) a pravú [c, b), pričom každú z nich nájdeme zvlášť.

Ak rozumieš tomu lineárnemu algoritmu, tak nájsť podpostupnosť s maximálnym súčtom so zafixovaným začiatkom/koncom by nemal byť problém.

Tuším podobná úloha (možno aj tá istá) je ako motivačný príklad na divide&conquer v tretej edícii Introduction to Algorithms.

Re: uloha 213

PoslaťNapísal: Pia Jún 22, 2012 10:53 am
od dzusik12
dik za pomoc, uz to bezi, v celku zaujimava uloha, odporucam preriesit tym co si to tu najdu...