| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
ivanzub
Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
|
|
| [Vrh] |
|
MKova
Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38)
Postovi: (187)16
Spol: 
|
|
| [Vrh] |
|
Raz
Forumaš(ica)
Pridružen/a: 07. 02. 2005. (22:40:23)
Postovi: (6F)16
Lokacija: Tamo gdje ribe jedu avanturiste...
|
 Postano: 13:59 ned, 10. 2. 2008 Naslov: |
    |
|
|
uredjeni parovi su za taj primjer: (element liste, njegov redni broj u listi)
mene zanima sortiranje liste pomocu hrpe silazno, jel to ovisi samo o tome kako na kraju ubacujemo u listu element koji vadimo iz hrpe sa DELETE_MIN? Znaci ili ga ubacujemo na pocetak liste ili na kraj ovisno o uzlazno/silazno, ili postoji neki drugi algoritam...
I zanima me dal se ti svi elementi nakon ubacivanja u hrpu brisu iz orginalne liste, pa sortirani vracaju u nju, ili se ubacuju u novu listu? Mozda ovo zadnje pitanje i nije toliko bitno,al zanima iz razloga sto su i orginalna i sortirana lista nazvane sa L, pa ispada kao da se brisu svi elementi orginalne liste.
uredjeni parovi su za taj primjer: (element liste, njegov redni broj u listi)
mene zanima sortiranje liste pomocu hrpe silazno, jel to ovisi samo o tome kako na kraju ubacujemo u listu element koji vadimo iz hrpe sa DELETE_MIN? Znaci ili ga ubacujemo na pocetak liste ili na kraj ovisno o uzlazno/silazno, ili postoji neki drugi algoritam...
I zanima me dal se ti svi elementi nakon ubacivanja u hrpu brisu iz orginalne liste, pa sortirani vracaju u nju, ili se ubacuju u novu listu? Mozda ovo zadnje pitanje i nije toliko bitno,al zanima iz razloga sto su i orginalna i sortirana lista nazvane sa L, pa ispada kao da se brisu svi elementi orginalne liste.
_________________
One good thing about music,when it hits: you feel no pain
|
|
| [Vrh] |
|
lyra
Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol: 
|
|
| [Vrh] |
|
Raz
Forumaš(ica)
Pridružen/a: 07. 02. 2005. (22:40:23)
Postovi: (6F)16
Lokacija: Tamo gdje ribe jedu avanturiste...
|
|
| [Vrh] |
|
lyra
Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol:
|
| Postano: 14:35 ned, 10. 2. 2008 Naslov: |
|
|
|
no da :D a wikipedija naprimjer kaže:
[quote]The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure. (...) “Greater than” means according to whatever comparison function is chosen to sort the heap, [b]not necessarily “greater than” in the mathematical sense[/b].[/quote]
al ajd, mi studiramo na pmf-mo-u, a ne sveučilištu vikipedija :lol:
EDIT: ipak se hrpe koriste i za druge stvari osim implementacije priority kjuija. :D ako samo trebaš napravit skicu kako se preko hrpe sortira lista (silazno), dakle ako nije programerski zadatak, valjda se ipak smije hrpa tako definirat.. to bi imalo smisla. :)
no da  a wikipedija naprimjer kaže:
| Citat: | | The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure. (...) “Greater than” means according to whatever comparison function is chosen to sort the heap, not necessarily “greater than” in the mathematical sense. |
al ajd, mi studiramo na pmf-mo-u, a ne sveučilištu vikipedija 
EDIT: ipak se hrpe koriste i za druge stvari osim implementacije priority kjuija. ako samo trebaš napravit skicu kako se preko hrpe sortira lista (silazno), dakle ako nije programerski zadatak, valjda se ipak smije hrpa tako definirat.. to bi imalo smisla. 
_________________
- Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
|
|
| [Vrh] |
|
ivanzub
Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
|
|
| [Vrh] |
|
MKova
Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38)
Postovi: (187)16
Spol:
|
| Postano: 16:43 ned, 10. 2. 2008 Naslov: |
|
|
|
hrpa nije povezana sa priority queuem vec sa binarnim stablom, kako pise u definiciji hrpe... isto tako hrpa nije nigdje definirana kao a.t.p., mozes napisati sto hoces glavno da zadovoljava definiciju.
i mozes imati DELETE_MAX, dapace na jednom od zadataka iz zadace bila je uputa da se to tako napravi (zamijeni totalni uredjaj unutar hrpe, => postaje <=). Na kraju mozes raditi sa delete_min pa umetati elemente na pocetak liste ili delete_max pa umetati na kraj liste.
kako je zadatak sortirati listu ja bih rekao da se ubacuju u istu listu, nakon sto je "resetiras" sa make_null.
hrpa nije povezana sa priority queuem vec sa binarnim stablom, kako pise u definiciji hrpe... isto tako hrpa nije nigdje definirana kao a.t.p., mozes napisati sto hoces glavno da zadovoljava definiciju.
i mozes imati DELETE_MAX, dapace na jednom od zadataka iz zadace bila je uputa da se to tako napravi (zamijeni totalni uredjaj unutar hrpe, => postaje <=). Na kraju mozes raditi sa delete_min pa umetati elemente na pocetak liste ili delete_max pa umetati na kraj liste.
kako je zadatak sortirati listu ja bih rekao da se ubacuju u istu listu, nakon sto je "resetiras" sa make_null.
_________________ suradnici za razvoj igre traženi!! vidi ovo |
|
| [Vrh] |
|
Raz
Forumaš(ica)
Pridružen/a: 07. 02. 2005. (22:40:23)
Postovi: (6F)16
Lokacija: Tamo gdje ribe jedu avanturiste...
|
| Postano: 15:51 pon, 11. 2. 2008 Naslov: |
|
|
|
[quote="MKova"]hrpa nije povezana sa priority queuem vec sa binarnim stablom, kako pise u definiciji hrpe... isto tako hrpa nije nigdje definirana kao a.t.p., mozes napisati sto hoces glavno da zadovoljava definiciju.
i mozes imati DELETE_MAX, dapace na jednom od zadataka iz zadace bila je uputa da se to tako napravi (zamijeni totalni uredjaj unutar hrpe, => postaje <=). Na kraju mozes raditi sa delete_min pa umetati elemente na pocetak liste ili delete_max pa umetati na kraj liste.
kako je zadatak sortirati listu ja bih rekao da se ubacuju u istu listu, nakon sto je "resetiras" sa make_null.[/quote]
ok...sve mi je to jasno...no i dalje ne znam kad me netko trazi da sortiram listu silazno, dal moram okrenuti hrpu naopako pa koristiti DELETE_MAX ili radim normalnu hrpu pa ubacujem elemente na pocetak liste?...
I zanima me jos zadataka iz proslogodisnjeg kolokvija s hash funkcijom,tj drugi zadatak...Kako izgleda zatvorena hash tabilica? Jel je oblika npr. 3. pretinac pa u njemu uredjeni par npr. 261735 "Pero" ili samo "Pero"?
I dal ako nije navedeno u svaki pretinac stane samo jedan element?
Hvala svim dobrim ljudima koji nicim izazvani odgovaraju na moja blesava pitanja, al takav sam ja,volim znat sitnice :D ...posebice kod SPA-a
| MKova (napisa): | hrpa nije povezana sa priority queuem vec sa binarnim stablom, kako pise u definiciji hrpe... isto tako hrpa nije nigdje definirana kao a.t.p., mozes napisati sto hoces glavno da zadovoljava definiciju.
i mozes imati DELETE_MAX, dapace na jednom od zadataka iz zadace bila je uputa da se to tako napravi (zamijeni totalni uredjaj unutar hrpe, ⇒ postaje ⇐). Na kraju mozes raditi sa delete_min pa umetati elemente na pocetak liste ili delete_max pa umetati na kraj liste.
kako je zadatak sortirati listu ja bih rekao da se ubacuju u istu listu, nakon sto je "resetiras" sa make_null. |
ok...sve mi je to jasno...no i dalje ne znam kad me netko trazi da sortiram listu silazno, dal moram okrenuti hrpu naopako pa koristiti DELETE_MAX ili radim normalnu hrpu pa ubacujem elemente na pocetak liste?...
I zanima me jos zadataka iz proslogodisnjeg kolokvija s hash funkcijom,tj drugi zadatak...Kako izgleda zatvorena hash tabilica? Jel je oblika npr. 3. pretinac pa u njemu uredjeni par npr. 261735 "Pero" ili samo "Pero"?
I dal ako nije navedeno u svaki pretinac stane samo jedan element?
Hvala svim dobrim ljudima koji nicim izazvani odgovaraju na moja blesava pitanja, al takav sam ja,volim znat sitnice ...posebice kod SPA-a
_________________
One good thing about music,when it hits: you feel no pain
|
|
| [Vrh] |
|
Luuka
Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
| Postano: 12:27 uto, 12. 2. 2008 Naslov: |
|
|
|
Ja bi sortiro listu silazno tako da ju sortiram uzlazno, klasičnim algoritmom, i ono što mi vrati DELETE_MIN spremam na stog. Na kraju samo povadim sve iz stoga i lista je sort silazno ;)
Nego, jel nam svejedno kad sortiramo listu, na koju stranu hrpe otiđe onaj čvor kojeg premjestimo u korijen? Jer na koju god stranu ode, ostat će hrpa (onim zamjenama)...
Ja bi sortiro listu silazno tako da ju sortiram uzlazno, klasičnim algoritmom, i ono što mi vrati DELETE_MIN spremam na stog. Na kraju samo povadim sve iz stoga i lista je sort silazno 
Nego, jel nam svejedno kad sortiramo listu, na koju stranu hrpe otiđe onaj čvor kojeg premjestimo u korijen? Jer na koju god stranu ode, ostat će hrpa (onim zamjenama)...
_________________ "Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy |
|
| [Vrh] |
|
ivanzub
Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
|
|
| [Vrh] |
|
Luuka
Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
| Postano: 12:51 uto, 12. 2. 2008 Naslov: |
|
|
|
Ako se dozvoli pomoćni stog, ono moje je ok. Dakle sortiraš uzlazno pomoću hrpe, i spremaš na stog ono što ti vrati fja DELETE_MIN. Onda prođeš po stogu dok nije prazan i ispisuješ što ti vrati POP -> silazno sort listu
A gore pitam za situaciju kad u korijen recimo dođe 8, a oba djeteta su 3. Jel onda svejedno na koju stranu mijenjam taj 8? Jer svakak ću dobit hrpu, samo će drugačije izgledat.
Ako se dozvoli pomoćni stog, ono moje je ok. Dakle sortiraš uzlazno pomoću hrpe, i spremaš na stog ono što ti vrati fja DELETE_MIN. Onda prođeš po stogu dok nije prazan i ispisuješ što ti vrati POP -> silazno sort listu
A gore pitam za situaciju kad u korijen recimo dođe 8, a oba djeteta su 3. Jel onda svejedno na koju stranu mijenjam taj 8? Jer svakak ću dobit hrpu, samo će drugačije izgledat.
_________________ "Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy |
|
| [Vrh] |
|
MKova
Forumaš(ica)
Pridružen/a: 01. 10. 2005. (18:24:38)
Postovi: (187)16
Spol:
|
| Postano: 13:22 uto, 12. 2. 2008 Naslov: |
|
|
|
[quote="Luuka"]Ako se dozvoli pomoćni stog, ono moje je ok. Dakle sortiraš uzlazno pomoću hrpe, i spremaš na stog ono što ti vrati fja DELETE_MIN. Onda prođeš po stogu dok nije prazan i ispisuješ što ti vrati POP -> silazno sort listu[/quote]
ne razumijem tu komplikaciju jos i sa stogom ako jednostavno mozes stavljati elemente na kraj ili poceak liste, ovisno da li se koristi delete_min ili delete_max.
[quote="Luuka"]
A gore pitam za situaciju kad u korijen recimo dođe 8, a oba djeteta su 3. Jel onda svejedno na koju stranu mijenjam taj 8? Jer svakak ću dobit hrpu, samo će drugačije izgledat.[/quote]
ako pricas o delete funkciji, onda nije svejedno jer je hrpa potpuno bin. stablo, dakle uvijek se brise desno dijete u slucaju da postoje oba dijeteta.
| Luuka (napisa): | | Ako se dozvoli pomoćni stog, ono moje je ok. Dakle sortiraš uzlazno pomoću hrpe, i spremaš na stog ono što ti vrati fja DELETE_MIN. Onda prođeš po stogu dok nije prazan i ispisuješ što ti vrati POP → silazno sort listu |
ne razumijem tu komplikaciju jos i sa stogom ako jednostavno mozes stavljati elemente na kraj ili poceak liste, ovisno da li se koristi delete_min ili delete_max.
| Luuka (napisa): |
A gore pitam za situaciju kad u korijen recimo dođe 8, a oba djeteta su 3. Jel onda svejedno na koju stranu mijenjam taj 8? Jer svakak ću dobit hrpu, samo će drugačije izgledat. |
ako pricas o delete funkciji, onda nije svejedno jer je hrpa potpuno bin. stablo, dakle uvijek se brise desno dijete u slucaju da postoje oba dijeteta.
_________________ suradnici za razvoj igre traženi!! vidi ovo |
|
| [Vrh] |
|
Luuka
Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
| Postano: 13:30 uto, 12. 2. 2008 Naslov: |
|
|
|
Al ne postoji fja delete_max, zato pomoćni stog...
A govorim o situaciji kad uklonimo najmanjeg, nek je to 2 i onda zadnji list u stablu preselimo u korijen. (to je desno dijete ako postoje oba)
Sad trebamo napravit one zamjene da opet dobijemo hrpu. Nek su sad djeca od te osmice 3 (oba djeteta). Sad dal je svejedno s kojom trojkom zamijenimo 8?
Al ne postoji fja delete_max, zato pomoćni stog...
A govorim o situaciji kad uklonimo najmanjeg, nek je to 2 i onda zadnji list u stablu preselimo u korijen. (to je desno dijete ako postoje oba)
Sad trebamo napravit one zamjene da opet dobijemo hrpu. Nek su sad djeca od te osmice 3 (oba djeteta). Sad dal je svejedno s kojom trojkom zamijenimo 8?
_________________ "Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy |
|
| [Vrh] |
|
Fisher
Forumaš(ica)
Pridružen/a: 09. 02. 2007. (23:38:24)
Postovi: (41)16
Lokacija: split
|
|
| [Vrh] |
|
desire
Forumaš(ica)
Pridružen/a: 06. 09. 2007. (07:46:21)
Postovi: (133)16
Spol:
|
| Postano: 14:37 uto, 12. 2. 2008 Naslov: |
|
|
|
Jedno pitanje....
Zadatak glasi ovako: napisite implementaciju funkcije MIN pod pretpostavkom da je skup (rjecnik) prikazan sa BST, a samo binarno stablo je implementirano pomocu pointera.
Ovo je rjesenje: [code:1]elementtype MIN (celltype *T) {
if (T->leftchild==NULL) return T->label;
else return MIN (T->leftchild);
}[/code:1]
Kuzim sto se radi, ali mi je ovaj return kod elsa uporno visak pa ako bi mi netko mogao objasniti zato ide taj return ili sam ja krivo prepisala.
Jer po mojoj logici on dodje do lista, jos jednom se pozove funkcija, nema djeteta i vrati vrijednost, ovaj drugi return je bespotreban. :?
Jedno pitanje....
Zadatak glasi ovako: napisite implementaciju funkcije MIN pod pretpostavkom da je skup (rjecnik) prikazan sa BST, a samo binarno stablo je implementirano pomocu pointera.
Ovo je rjesenje: | Kod: | elementtype MIN (celltype *T) {
if (T->leftchild==NULL) return T->label;
else return MIN (T->leftchild);
} |
Kuzim sto se radi, ali mi je ovaj return kod elsa uporno visak pa ako bi mi netko mogao objasniti zato ide taj return ili sam ja krivo prepisala.
Jer po mojoj logici on dodje do lista, jos jednom se pozove funkcija, nema djeteta i vrati vrijednost, ovaj drugi return je bespotreban. 
_________________  |
|
| [Vrh] |
|
lyra
Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol:
|
| Postano: 14:53 uto, 12. 2. 2008 Naslov: |
|
|
|
meni se čini ok.. funkcija prima korijen stabla, ako taj korijen nema lijevog djeteta onda je najmanji element u stablu upravo u korijenu (zbog svojstva bin.stabla traženja), pa vraća element iz korijena. ako korijen ima lijevo dijete, onda mora ić u lijevo podstablo tražit najmanji element.
meni se čini ok.. funkcija prima korijen stabla, ako taj korijen nema lijevog djeteta onda je najmanji element u stablu upravo u korijenu (zbog svojstva bin.stabla traženja), pa vraća element iz korijena. ako korijen ima lijevo dijete, onda mora ić u lijevo podstablo tražit najmanji element.
_________________
- Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
|
|
| [Vrh] |
|
desire
Forumaš(ica)
Pridružen/a: 06. 09. 2007. (07:46:21)
Postovi: (133)16
Spol:
|
| Postano: 14:57 uto, 12. 2. 2008 Naslov: |
|
|
|
[quote="lyra"]meni se čini ok.. funkcija prima korijen stabla, ako taj korijen nema lijevog djeteta onda je najmanji element u stablu upravo u korijenu (zbog svojstva bin.stabla traženja), pa vraća element iz korijena. ako korijen ima lijevo dijete, onda mora ić u lijevo podstablo tražit najmanji element.[/quote]
Pa da, kuzim to, ali onda kod onog else ne treba return MIN(...) nego samo else MIN (....). Kuzis sta mi nije jasno?
Sve ovo ima dijete, nema dijete i procedura po kojoj trazi mi je jasna, ali ne kuzim funkciju ovog return. Return iza if-a mi je jasan, vraca najmanjeg, ali cemu ovaj drugi return kad se tako i tako opet poziva jedno te ista funkcija, samo sa djetetom? :?
| lyra (napisa): | | meni se čini ok.. funkcija prima korijen stabla, ako taj korijen nema lijevog djeteta onda je najmanji element u stablu upravo u korijenu (zbog svojstva bin.stabla traženja), pa vraća element iz korijena. ako korijen ima lijevo dijete, onda mora ić u lijevo podstablo tražit najmanji element. |
Pa da, kuzim to, ali onda kod onog else ne treba return MIN(...) nego samo else MIN (....). Kuzis sta mi nije jasno?
Sve ovo ima dijete, nema dijete i procedura po kojoj trazi mi je jasna, ali ne kuzim funkciju ovog return. Return iza if-a mi je jasan, vraca najmanjeg, ali cemu ovaj drugi return kad se tako i tako opet poziva jedno te ista funkcija, samo sa djetetom?
_________________ |
|
| [Vrh] |
|
ivanzub
Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
|
|
| [Vrh] |
|
lyra
Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol:
|
| Postano: 15:04 uto, 12. 2. 2008 Naslov: |
|
|
|
hmm.. vjerojatno bi štimalo i bez tog return, ali možda postoji neki dubokoumni razlog zašto ga ipak treba stavit. :lol: ajd, nek se javi netko pametniji pa nas prosvijetli :D
EDIT: možda treba pisat return jer se funkcija stalno rekurzivno poziva, a na kraju treba originalna funkcija, a ne njen 5. ili 6. rekurzivni poziv vratit vrijednost.. tj., return šalje traženu vrijednost iz "terminalnog" poziva sve do onog originalnog. inače se nikad ne bi izašlo iz tog originalnog poziva (iako bi program obavio ono kaj treba obavit).
al čini mi se da se trenutno ne trebamo oko *ovog* zabrinjavat.. :lol:
hmm.. vjerojatno bi štimalo i bez tog return, ali možda postoji neki dubokoumni razlog zašto ga ipak treba stavit. ajd, nek se javi netko pametniji pa nas prosvijetli
EDIT: možda treba pisat return jer se funkcija stalno rekurzivno poziva, a na kraju treba originalna funkcija, a ne njen 5. ili 6. rekurzivni poziv vratit vrijednost.. tj., return šalje traženu vrijednost iz "terminalnog" poziva sve do onog originalnog. inače se nikad ne bi izašlo iz tog originalnog poziva (iako bi program obavio ono kaj treba obavit).
al čini mi se da se trenutno ne trebamo oko *ovog* zabrinjavat..
_________________
- Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
Zadnja promjena: lyra; 15:18 uto, 12. 2. 2008; ukupno mijenjano 1 put.
|
|
| [Vrh] |
|
|
