Priklad na haldu ve skriptech
- Hugo
- 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:
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..
"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..
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
My jsme prave na cvikach s tim jednim mistem navic pocitali. To znamena ze Zemlicka razi stejnou vec, jako tu pred chvili napsal Anonymni?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..
Hlavne je to peknej vopruz ... rvat se o 1 misto v pameti, kdyz mas 1GB
Plug 'n' Pray.
- Almer
- Site Admin
- Příspěvky: 686
- Registrován: 12. 10. 2004 10:58
- Typ studia: Informatika Ph.D.
- Login do SIS: lasap4am
- Bydliště: Mala Strana - 203
- Kontaktovat uživatele:
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
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
Zakládající člen klubu Ortodoxních Matfyzáků
Jsem LAMER ale neumim se ani podepsat ]
Jsem LAMER ale neumim se ani podepsat ]
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 vystupKeleen 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.
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
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
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..
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 ).
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
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;)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 ).