Priklad na haldu ve skriptech

Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Priklad na haldu ve skriptech

Příspěvek od Keleen »

Nedelali jste nekdo nahodou ten priklad na strane 39, priklad 2.9?
Ja jsem ho zkousel, precetl jsem si ten postup asi 4x, ale porad nejsem schopen dojit ke stejnemu vysledku, co tam je.Konkretne, kdyz prichazi na vstup cislo 11, tak ja tesne pred tim priradim do vystupniho souboru cislo 26 a 11 se mi tak zaradi az do druheho behu.
Nemohli byste mi nekdo prosim naznacit kde delam chybu, nebo alespon rict v tech skriptech je to dobre, me to vyslo, nekde neco kiksujes?
Diky moc.
schaschek
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 13. 6. 2006 17:33

Příspěvek od schaschek »

Mně to taky nevyšlo a řekl bych, že chyba bude nejspíš ve skriptech. Moc nechápu, jak vůbec mohli něco takovýho vydat; a to nemluvím o nějaké té chybce, která se vždycky vloudí, ale vůbec o stylu, kterým jsou napsaný. Taky to mohli podat trošku lidštější formou :evil:
No tak jsem si zanadával a výsledek je podle mě tento: 1, 6, 8, 26, 36, 38, 42, 47, 88, 95 a 2, 4, 11, 15, 29
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Taky mi to tak vyšlo....
Uživatelský avatar
Tajro
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 14. 2. 2006 08:23
Typ studia: Informatika Bc.
Bydliště: Praha, Morava
Kontaktovat uživatele:

Příspěvek od Tajro »

Mně taky tak.. No snad nejsme všichni úplně natvrdlí.. :) Řekl bych, že jsem se přesně držel slovního postupu a tak musí být ve skriptech chyba (další).. no shodlo se nás na tom už víc, tak to považuji za vyřešenou věc :)
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Souhlas :) ... me se nechtelo to delat cely, ale uz kdyz jsem si vyrobil tu pocatecni haldu tak mam oproti vypracovani prohozene prvky 38 a 26 ... takze hadam ze tady je zarodek problemu ... :?
Plug 'n' Pray.
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

take jsem to zkoumal radnou dobu a cetl mnohokrat a nakonec mi doslo, ze spatne (nebo spise matoucne) ma jen ten obrazek na str. 40.
Ve skriptech se presne pise, ze zapisete prvek na vystup a s tim porovnavate. Takze ta 11 se ma porovnavat s 8 a pokud je 11 >= 8, tak zapsat 11 na vrchol haldy (misto 8, ktera tam jakoby jeste furt je!), a haldu urovnat..

Co jsem resil jeste dele bylo, jak a s cim se porovnava, kdyz se prave postavi halda.. Napr. dle popisu ve skriptech mate s 3prvkovou haldou a 5,6,7,1 - 2 behy (protoze se musi zapsat na vystup a s tim az porovnavat, to znamena tu 1 nejde strcit na vystup hned). Psal jsem i Zemlickovi a odepsal, ze je to tak dobre..
Uživatelský avatar
Tajro
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 14. 2. 2006 08:23
Typ studia: Informatika Bc.
Bydliště: Praha, Morava
Kontaktovat uživatele:

Příspěvek od Tajro »

Hugo, potřeboval bych jednu věc upřesnit, předem díky.. U toho příkladu ve skriptech se dostaneme do stavu haldy (souhlasíš?):

Kód: Vybrat vše

                       8
             26               42
       36      38       95      47
  88
První běh: 1, 6
Vstup: 2, 11, 4, 15, 29

Teď nastala chvíle vypsat do prvního běhu kořen 8, tak ho vypíšeme!
Ale čím ho nahradíme?.. podle toho, co se píše ve skriptech,
nahradíme kořen posledním prvkem haldy, protože 2 < 8..
Potom haldu přerovnáme:

Kód: Vybrat vše

                      26
             36               42
       88      38       95      47
  [2]
No a co teď? Já bych normálně vypsal na výstup kořen a pak si dále četl, co je ve vstupu, jenže tím by se můj výsledek začal lišit od toho ve skriptech... další v běhu má být číslo 11.. ale jak můžu číst vstup, když pro něj nemám v haldě místo??? Má někdo nějaký nápad? Opravdu je ve výsledku ve skriptech chyba nebo ne?
Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Příspěvek od Keleen »

Hugo píše:take jsem to zkoumal radnou dobu a cetl mnohokrat a nakonec mi doslo, ze spatne (nebo spise matoucne) ma jen ten obrazek na str. 40.
Ve skriptech se presne pise, ze zapisete prvek na vystup a s tim porovnavate. Takze ta 11 se ma porovnavat s 8 a pokud je 11 >= 8, tak zapsat 11 na vrchol haldy (misto 8, ktera tam jakoby jeste furt je!), a haldu urovnat..

Co jsem resil jeste dele bylo, jak a s cim se porovnava, kdyz se prave postavi halda.. Napr. dle popisu ve skriptech mate s 3prvkovou haldou a 5,6,7,1 - 2 behy (protoze se musi zapsat na vystup a s tim az porovnavat, to znamena tu 1 nejde strcit na vystup hned). Psal jsem i Zemlickovi a odepsal, ze je to tak dobre..
Tak ted jsi me popravde docela zmatl.Podle me 8 zapisuji do souboru v dobe kdy prichazi 2.Tedy abych z toho udelal nejaky rozumny soupis to rozepisu do stavu:

STAV 1
v halde: 8 26 42 36 38 95 47 88
na vystupu: 1 6 8 // na konci predesleho kroku jsem akorat zapsal 8
na vstupu: 2 11 4 15 29

KROK
1) prectu ze vstupu 2
2) 2<8 tedy zkratim haldu o 1 stav
v halde: 88 26 42 36 38 95 47 | 2
3) urovnam haldu
v halde: 26 36 42 88 38 95 47 | 2
4) minimem v hlade se stalo 26, zapisu na vystup

STAV 2
v halde:26 36 42 88 38 95 47 | 2
na vystupu: 1 6 8 26
na vstupu: 11 4 15 29

KROK
1) prectu 11 // a ted proste musim porovnavat s 26, bo 8 uz je davno pryc...a nebo jsem nekde mimo?
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

pred chvili jsem byl upozornen, ze jsem take napsal jednu nepresnost:) Tady je problem, ze nemuzeme drzet tu 8 navrchu a musime prerovnavat a vzniklou situaci skripta vubec nepopisuji :roll:
Ale rekl bych, ze se vzdy porovnava s prave zapsanym prvkem, takze k tvemu prikladu.
Muzu se samozrejme mylit.
Podle me, kdyz zarazujes 2, tak ji porovnavas se 6 (ktera je prave zapsana) a kdyz zarazujes tu 11, tak ji porovnavas s 8 a ne 26 - snad jsem to napsal srozumitelne.

Jak si to Zemlicka predstavuje s pameti je otazka, protoze podle tohoto postupu budeme v tomto pripade potrebovat 2 nova mista mimo haldu :shock: .. Ale k lepsimu se asi ani nedostaneme, vzdy nejake to misto pro porovnani prichoziho prvku navic potrebujeme.
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

popravde receno si myslim, ze to tak je, protoze to je "rozumejsi" reseni a protoze to potom vyjde lepe a take to vyjde jako ve skriptech..
Predpokladam, ze by si snad Zemlicka za ty 2-3 roky nevsiml takove do oci bijici chyby, pokud by ji opravdu byla :lol:
Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Příspěvek od Keleen »

Me se take zda divne ze by tu chybu nikdo driv neobjevil, ale nemuzu si pomoct...podle postupu ve skriptech urovnas haldu, zapises na vystup prvni prvek a ctes prvni vstup:
1) zapisuji 1 a ctu 88
Pak podle postupu zaradim 88 do korene a urovnam haldu.Nove vznikle minimum zapisu do souboru a ctu dalsi vstup
2) zapisuji 6 a ctu 42
42 je vetsi nez 6, prijde do korene a urovnam haldu, novym minimem je 8 tak ho zapisu a ctu dalsi vstup
3) zapisuji 8 a ctu 2
2 nevyhovuje, zkrati mi haldu o 1 prvek, halda se prerovna, na vrchol se dostane 26...a tu ted podle me mam zapsat a cist dalsi vstup
4) zapisuji 26 a ctu 11
Mno a jsem v haji...jsem uz z toho celej tumpachovej, prosim, jestli nekdo tu moji chybu vidite, vypichnete ji nasvetlo...diky.
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

nj, uz to vidim...tak to ma asi fakt blbe :lol:
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

myslim Zemlicka a ja jsem se blbe prehlid..
Návštěvník

Příspěvek od Návštěvník »

Hugo píše: Jak si to Zemlicka predstavuje s pameti je otazka, protoze podle tohoto postupu budeme v tomto pripade potrebovat 2 nova mista mimo haldu :shock: .. Ale k lepsimu se asi ani nedostaneme, vzdy nejake to misto pro porovnani prichoziho prvku navic potrebujeme.
Navíc stejnou službu jako pamatování si posledního prvku zapsaného na výstup by ti udělala i o jedna větší halda. My jsme to sice na cvičení dělali taky tak, že jsme se dívali, jestli náhodou vstup není větší než poslední zapsaný na výstup a současně menší než vršek haldy, a případně jsme ho nacpali na výstup mezi ně, ale je to blbost.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Hugo píše:Co jsem resil jeste dele bylo, jak a s cim se porovnava, kdyz se prave postavi halda.. Napr. dle popisu ve skriptech mate s 3prvkovou haldou a 5,6,7,1 - 2 behy (protoze se musi zapsat na vystup a s tim az porovnavat, to znamena tu 1 nejde strcit na vystup hned). Psal jsem i Zemlickovi a odepsal, ze je to tak dobre..
To znamena ze kdyz v pisemce strcim na vystup 1 hned tak mam chybu? To je teda pekne sahly ... vzdyt ten algoritmus je funkcni a lepsi -- indikace toho ze zadny vystup jsem nemel tam musi byt tak jako tak a je jen na me co s tim udelam, jestli 1 v takovem pripade strcim na vystup a nebo na konec haldy :(
Plug 'n' Pray.
Odpovědět

Zpět na „2006“