Domáca úloha č. 3, riešenia úlohy č. 1

Moderátor: FeroG

<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Pia Mar 14, 2008 4:26 pm

Domáca úloha č. 3, riešenia úlohy č. 1

Na stránke cvičení (sekcia Domáce úlohy) je k dispozícii pracovný list č. 3.
Okrem toho tam nájdete nejaké riešenia k listu č. 1. Z každého prístupu som sa snažil vybrať nejakého reprezentanta. Niektoré pekné riešenia sa nedostali do výberu nie preto, že neboli dostatočne pekné, ale preto, že prípadných čitateľov by mnoho riešení zmiatlo a tiež som sa snažil vybrať nejaké typické príklady prístupu k problému. V niektorých vybraných riešeniach sa nájdu aj chybičky, ale skôr si treba všímať myšlienku. Vždy platí, že svoje riešenia môžete na tomto fóre zverejniť po uplynutí deadlinu (+ pár dní pre oneskorencov).

Komentáre k riešeniam:
Ján Jerguš: vysoko optimalizované riešenie Sudoku. Všimnite si, ako sa pomocou pomocných polí ušetril čas na testoch.
Pavel Balint: sudoku kombinované s objektami.
Monika Krausová: prístup generuj/spracuj
Beáta Katuščáková: klasické rekurzívne riešenie (väčšina riešení využila tento prístup) s pekným rozdelením problému do metód

Komentáre, otázky, pripomienky ?
<<

Shadow

Príspevky: 3

Registrovaný: Pon Feb 25, 2008 9:23 pm

Poslať Pia Mar 14, 2008 10:52 pm

Re: Domáca úloha č. 3, riešenia úlohy č. 1

FeroG píše:Ján Jerguš: vysoko optimalizované riešenie Sudoku. Všimnite si, ako sa pomocou pomocných polí ušetril čas na testoch.

:idea: Heh, to riesenie sudoku s pomocnymi polami je super :) A pritom na prednaske sa to pouzivalo na tych 8 dam ...
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Sob Mar 15, 2008 12:49 pm

K domácej úlohe 3, StabilnePriradenie.java. Toto nezbehne:

  Kód:
Collections.shuffle(Arrays.asList(muzi[i].preferencie))


  1. Spraví to z čohosi zoznam, potom ho zashuffluje a potom si ho garbage collector veselo pozbiera.
  2. asList(int[]) nezbehne, pretože int[] nie je instanceof Object[]. V 1.5 a novších Javách, kde asList podporuje variabilný počet argumentov, to spraví List s jedným int[] prvkom.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Sob Mar 15, 2008 10:08 pm

Dakujem za upozornenie a ospravedlnujem sa za kod vygenerovany k ulohe o stabilnych priradeniach. Tak to vyzera, ked sa pise kod rychlo a pisatel si neda namahu to za sebou skontrolovat (neberte si prosim z toho priklad). Na webe je uz aktualizovana verzia.

Detaily problemu (ak by to niekoho zaujimalo):
V skutocnosti problem nebol priamo ani v bode 1, ani v bode 2 (to su len dosledky). Akurat namiesto ziaduceho Integer[] som tam pouzil int[]. Aj preto je dobre zvyknut si pri praci s JCF nemixovat wrapovacie triedy a primitivne typy.
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Ned Mar 16, 2008 10:13 am

FeroG píše:Detaily problemu (ak by to niekoho zaujimalo):
V skutocnosti problem nebol priamo ani v bode 1, ani v bode 2 (to su len dosledky). Akurat namiesto ziaduceho Integer[] som tam pouzil int[]. Aj preto je dobre zvyknut si pri praci s JCF nemixovat wrapovacie triedy a primitivne typy.


Máš pravdu, bod 1 neplatí. Nevšimol som si, že zmeny v Liste vygenerovanom cez Arrays.asList sa priamo zapisujú do pôvodného poľa. To je celkom cool :)
E-mail/Jabber: jan[zavináč]jergus.eu
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Ned Mar 16, 2008 7:01 pm

K úlohe Cykly v grafoch: Stačí vypísať jeden ľubovoľný cyklus?
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Ned Mar 16, 2008 7:10 pm

Ano, staci lubovolny cyklus (bez opakovania vrcholov, s opakovanim vrcholov sa to nazyva uzavrety sled).

O tom ako to spravit (to sa netyka johnyho), sa mozeme bavit v utorok na cviceni (kedze to suvisi s topologickym triedenim).
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Uto Mar 25, 2008 8:47 pm

Dostal som jednu zaujimavu otazku tykajucu sa ulohy hladania cyklov v orientovanom grafe. Kedze to moze zaujimat aj dalsich, otazku som sa rozhodol zverejnit. Ak sa nenajde nikto, kto bude odpovedat, casom pripojim svoju odpoved.
Algoritmus navrhnuty na cviceni:
1. na grafe realizujem topologicke triedenie (odstranovanie vrcholov bez predchodcov). Ak skoncim s prazdnym grafom, tak graf nema cyklus.
2. vo zvysku grafu (pozostatok topologickeho triedenia) zvolim lubovolny vrchol
3. neustale "cuvam" po hranach startujuc vo zvolenom vrchole, az kym nepridem do nejakeho vrcholu X, ktory pri "cuvani" navstivim po druhy krat. Postupnost navstivenia vrcholov zacinajuca X a konciaca druhou navstevou X predstavuje cyklus v grafe (v opacnom poradi).

Otazky: Je nutne po hranach "cuvat" ? Neda sa ist v bode 3 len "dopredu" ?
Zalezi na tom, aku hranu pri "cuvani" vyberiem ? Alebo treba skusat vsetky ?
Je pravdou, ze vrchol X je v skutocnosti vzdy vrchol, z ktoreho som vystartoval pri "cuvani" ?
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Uto Mar 25, 2008 10:48 pm

FeroG píše:Je nutne po hranach "cuvat" ? Neda sa ist v bode 3 len "dopredu" ?

Obrázok
Takýto graf môže ostať po nedokončenom topologickom triedení. Z vrcholu A sa nikam dopredu nedostaneme. Vrcholy, z ktorých sa nikam nedostaneme cúvaním, nemôžu existovať - o to sa postará (nedokončené) topologické triedenie. (Každý vrchol má nejakého predchodcu, no nie každý musí mať nejakého následníka.)

FeroG píše:Zalezi na tom, aku hranu pri "cuvani" vyberiem ? Alebo treba skusat vsetky ?

Argument uvedený (tuším mnou :)) na cvičeniach sa neopieral o to, ktorú hranu si zvolíme. Opieral sa len o to, že
  1. každý vrchol má predchodcu, a
  2. vrcholov je konečný počet.
Z týchto dvoch predpokladov jasne vyplýva, že
  1. algoritmus sa nikdy nezastaví kvôli tomu, že by nemal kam ďalej ísť (vyplýva z 1) a
  2. algoritmus "príde" po najviac N krokoch (kde N je počet vrcholov, ktoré v grafe zostali) do niektorého vrcholu druhýkrát (vyplýva z 1 a 2).
Teda nezáleží na tom, ktorú spätnú hranu si zvolíme (môžeme tak však nájsť rôzne cykly).

FeroG píše:Je pravdou, ze vrchol X je v skutocnosti vzdy vrchol, z ktoreho som vystartoval pri "cuvani" ?

Nie, viď graf vyššie. Ak začneme vo vrchole A, dostaneme sa po 4 krokoch druhýkrát do vrcholu B (do vrcholu A sa nedá nijak vrátiť).
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 26, 2008 7:51 am

Dakujem Johnymu za pekne a jasne odpovede na otazky. A teraz este jedna otazka (poprosim Johnyho s odpovedou 2 dni pockat, mozno sa najde niekto iny, kto by to rad zodpovedal): Ak by som z nejakych dovodov v bode 3 chcel nie "cuvat", ale ist dopredu po hranach, bolo by to mozne ? Co by trebalo v algoritme upravit, resp. ako by trebalo algoritmus upravit ?
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Pia Mar 28, 2008 5:05 pm

FeroG píše:Ak by som z nejakych dovodov v bode 3 chcel nie "cuvat", ale ist dopredu po hranach, bolo by to mozne ? Co by trebalo v algoritme upravit, resp. ako by trebalo algoritmus upravit ?


Nezačať topologickým triedením, ale upraveným algoritmom, ako v úlohe o politikoch (postupne vyhadzovať z grafu vrcholy, ktoré nemajú následníkov, až kým neostanú len vrcholy s následníkmi alebo nič) - analogickými argumentmi ako v predošlom prípade pri cúvaní teraz vieme ukázať, že bude fungovať chodenie dopredu.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

ScortY

Príspevky: 5

Registrovaný: Pon Dec 04, 2006 4:33 pm

Poslať Sob Apr 05, 2008 10:18 am

nedali by sa tie cykli riesit aj tak ze by sme to topologicky utriedili "od zadu"aj "od predu"(kym by sa dal) nezostal by nam cisty cyklus?

edit: a tak nic,, mohlo by byt viac cyklov a nemuseli by byt jeden a ten isty.. ale zasa v tomto pripade by sme si mohli vybrat ci budeme cuvat alebo by sme isli do predu s tym ze by stacilo testovat iba jeden vrchol
<<

johny

Príspevky: 132

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

Bydlisko: Košice

Poslať Pon Apr 07, 2008 5:39 pm

ScortY píše:nedali by sa tie cykli riesit aj tak ze by sme to topologicky utriedili "od zadu"aj "od predu"(kym by sa dal) nezostal by nam cisty cyklus?

edit: a tak nic,, mohlo by byt viac cyklov a nemuseli by byt jeden a ten isty.. ale zasa v tomto pripade by sme si mohli vybrat ci budeme cuvat alebo by sme isli do predu s tym ze by stacilo testovat iba jeden vrchol


To nie je pravda.
Obrázok
Po obojstrannom vyhádzaní vrcholov ti môže ostať niečo takéto - červený vrchol nie je súčasťou žiadneho cyklu.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Apr 10, 2008 6:46 pm

Na stranke s domacimi ulohami su uz nejake riesenia k listom 2 a 3. Minimalne doporucujem pozriet sa na riesenia uloh tykajucich sa O-notacie a ulohy o hladani cyklov.

Späť na PAZ1b

Kto je on-line

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

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