Priklad na haldu ve skriptech

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 »

to byla Zemlickova odpoved
"To bych pak potreboval jeste jedno misto, kde bych si pamatoval, co jsme do toho behu naposledy zapsal. Pokud bych to nekontroloval, mohl bych vytvaret neusporadane "behy" ... Pokud mam to jedno misto na kontrolu, davam prednost ho mit zaroven k dispozici v te halde, pred tim jej mit zcela oddelene."

podle me by stacil jen boolean na kontrolovani, zda neni prave nova halda..
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:to byla Zemlickova odpoved
"To bych pak potreboval jeste jedno misto, kde bych si pamatoval, co jsme do toho behu naposledy zapsal. Pokud bych to nekontroloval, mohl bych vytvaret neusporadane "behy" ... Pokud mam to jedno misto na kontrolu, davam prednost ho mit zaroven k dispozici v te halde, pred tim jej mit zcela oddelene."

podle me by stacil jen boolean na kontrolovani, zda neni prave nova halda..
My jsme prave na cvikach s tim jednim mistem navic pocitali. To znamena ze Zemlicka razi stejnou vec, jako tu pred chvili napsal Anonymni?

Hlavne je to peknej vopruz ... rvat se o 1 misto v pameti, kdyz mas 1GB :)
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 »

Takze Zemlicka odepsal, ze ma opravdu ve skriptech tu chybu:))
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Příspěvek od Almer »

Kua, co tu zase melete?

Je to jasne...mam haldu, najdi minumum.

To zapisu na BEH. Podivam se na vystup a porovnam to s tim co mam stale na vrchole.

Je to spatne? (mensi, kdyz delam minimalne, a nebo vetsi , kdyz delam maximalne?), tak vyndam to cislo, co jsem zapsal, dam nejpravetsiho na vrchol a uriznu hladu (zacnu tam stavet druhou)

A kdyz to neni spatne, tak to tam dan na jeho misto a pak jen prorotuju a jsem v pohode 8)
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
gofry
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 13. 1. 2006 23:41

Příspěvek od gofry »

Mne skôr príde divné, že v skriptách je napísané, že v pamäti je miesto iba pre 8 prvkov. Tzn. ak vytvoríme haldu o veľkosti 8, tak žiadny ďalší vstup už do pamäte nenačítame a nemôžeme nič robiť. Musíme teda vytvoriť haldu o veľkosti 7 a do ôsmeho miesta načitávame vstup.
christyna
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 25. 1. 2006 18:31

Příspěvek od christyna »

Keleen píše: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.
tak ja nevim, me to prijde ve skriptech dobre.. a logictejsi, nez tu pisete.. protoze pokud je prvek na vstupu mensi nez nejmensi prvek v halde, tak ho rovnou dam na vystup

takze pokud vezmu fazi 4.. tak 11 porovnam s 26.. a zjistim, ze je mensi a proto tu 11 poslu na vystup a podobne to bude i s temi ostatni cisly. Nebo uz opravdu nevim
Uživatelský avatar
gofry
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 13. 1. 2006 23:41

Příspěvek od gofry »

christyna: A čo ak posledný zapísaný prvok bol 25? Zapísanie 11 na výstup ti pokazí beh. Porovnanie vstupu a haldy ti teda nestačí.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

tak tak.. dalo by se pamatovat tedy co je poslední zapisovaný prvek, ale to by pak bylo prakticky totéž jako zvětšit haldu o jedna, .. jediná otázka je, jestli se to smí udělat s prvním prvkem běhu (tam to nevadí), ... dokonce v loňské písemce to byl i rozdílný výsledek (2 nebo 3 běhy), ale myslím, že takové vylepšení se nedělalo a u zkoušky ho nechce..
Uživatelský avatar
gofry
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 13. 1. 2006 23:41

Příspěvek od gofry »

S prvým prvkom by sa to síce dalo, ale musel by som si pamätať, či som už na výstup čosi zapísal alebo nie, a na to nemám pamäť. Takže nedokážem rozlíšiť, či sa nachádzam na začiatku alebo v strede zapisovania. (Aby som príliš nekecal, tak ja som proste neprišiel na spôsob, ako to zistiť, čo samozrejme neznamená, že to nejde ;-)).
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

gofry píše:S prvým prvkom by sa to síce dalo, ale musel by som si pamätať, či som už na výstup čosi zapísal alebo nie, a na to nemám pamäť. Takže nedokážem rozlíšiť, či sa nachádzam na začiatku alebo v strede zapisovania. (Aby som príliš nekecal, tak ja som proste neprišiel na spôsob, ako to zistiť, čo samozrejme neznamená, že to nejde ;-)).
No tak 1. varianta je vyhradit na to bit kdesy, když bys to fakt rval do posledního bitu, ten se vždy někde najde, 2.varianta je holt vytáhnout ten 1. krok před cyklus a mít tam spec. podmínku;), což výjde ve finále paměťově náročnější (kód někde taky musím mít), ale efektivnější.. ale v mergesortu zrovna jedno porovnani v kazdem kroku navic neni zas takova zatez a ten potencialne usetreny beh stoji za zvazeni;)
Odpovědět

Zpět na „2006“