uloha 213

Moderátor: FeroG

<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Ned Jún 17, 2012 9:49 pm

uloha 213

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
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Ned Jún 17, 2012 11:05 pm

Re: uloha 213

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).
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Ned Jún 17, 2012 11:39 pm

Re: uloha 213

ale praveze linearne riesenie chapem, ale to n log n sa pytam ze jak
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Pon Jún 18, 2012 12:01 am

Re: uloha 213

Aha, ja uz v poslednom case neviem ani citat :)
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Uto Jún 19, 2012 9:47 am

Re: uloha 213

taze nevie nikto jak to zriesit cez rozdeluj a panuj ?
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Uto Jún 19, 2012 2:30 pm

Re: uloha 213

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.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Pia Jún 22, 2012 10:53 am

Re: uloha 213

dik za pomoc, uz to bezi, v celku zaujimava uloha, odporucam preriesit tym co si to tu najdu...

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 1 hosť

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.