Forum@DeGiorgi :: Pogledajte temu - Objavljeni su zadaci za vjezbu za 2. kolokvij...

Objavljeni su zadaci za vjezbu za 2. kolokvij...

through

[^/[Print]\]

Forum@DeGiorgi -> Strukture podataka i algoritmi

#1: Objavljeni su zadaci za vjezbu za 2. kolokvij... Autor/ica: Zvone,

Postano: 22:44 uto, 30. 1. 2007
—
...i mozete ih pronaci ovdje.

Mala opaska: zadaci su vecinom sa pismenih ispita gdje su neki od njih spadali pod "one za pet", znaci medju njima ima i nesto tezih. Da budem malo precizniji:
– zadaci 1-5 bi trebali biti prilicno jednostavni
– zadatak 6 je nesto malo tezi (osim onog dijela "ako ne znate" koji je lagan)
– zadatak 7 pod (a) i (b) je jako lagan, pod (c) je zvjezdica (sto znaci da je za one koji zele znati vise Smile

)
– dio sa dinamickim programiranjem u zadacima 8, 9 i 10 se rjesava na nacin posve slican onom sto je opisano u skripti i uputama koje su stavljene na web za zadatke iz zadace; u 10-om je nesto teze smisliti rekurzivnu formulu
– dio sa pohlepnim algoritmima u zadacima 8-11 je trivijalan
– 12 je lagani backtracking, a 13 malo slozeniji
– zvjezdica u 12(c) je samo zato sto vam nije unaprijed napisana funkcija za koju treba naci rekurzivnu formulu.

Evo, sada imate nesto materijala za vjezbanje. Ne mogu obecati da cemo objaviti rjesenja nekih zadataka kao prosli put jer sam malo u guzvi sa drugim stvarima...Ali slobodno dodjite na konzultacije ako negdje zapnete.

#2: Autor/ica: Greda,

Postano: 23:20 sub, 3. 2. 2007
—
hoće li teorijski dio u drugom kolokviju biti istog tipa kao što je bio u prvom kolokviju?

hvala

#3: Autor/ica: kika,

Postano: 23:24 sub, 3. 2. 2007
—
mislim da je u utorak rekao prof.da hoce,1.zadatak tipa zadnjeg zadatka na 1.kolokviju.
a na zavrsnom ispitu ce biti takva 2zadatka.

#4: Autor/ica: Greda,

Postano: 23:38 sub, 3. 2. 2007
—
u režimu piše da će biti 3 teorijska zadatka

#5: Autor/ica: Debla,

Postano: 21:22 uto, 6. 2. 2007
—
jel neko rjesavao mozda zadatke... mene bi interesiralo dal u drugom zadatku mozemo hrpu tako napravit da je na vrhu max, tj. da je roditelj veci il jednak djetetu.. pa onda umjesto DELETE_MIN koristima DELETE_MAX... mislim kao brisemo korjen..

i dal neko zna kako mozemo kod MAPPINGA doc do recimo d i M(d)?

#6: Autor/ica: andreao, Lokacija: SK

Postano: 11:39 čet, 8. 2. 2007
—
Pa rekao je profesor da će biti 3 zadatka na završnom koliko se meni čini.
Imate na oglasnoj ploči obješene bodove za sudjelovanje u nastavi. Idu od 0 do 5.

#7: Autor/ica: mladac, Lokacija: zg

Postano: 11:57 čet, 8. 2. 2007
—
jel ima ko problema sa ovim zadacima? meni već dva dana zeza! otvorim ih al mi počne javljat greške i samo taj prozor mi zablokira i ne mogu ga ubiti... niti isprintat... jel mi može neko poslat te zadatke na mail... pliz

#8: Autor/ica: Debla,

Postano: 16:51 čet, 8. 2. 2007
—
ljudi.. trebam pomoci neznam rješit ove zadake s dinamičkim programiranjem

točnije 8.,9. i 10... aj neka se javi neka dušica koja mi može objasnit.. il još bolje stavit rješenje i objasnit.. poludit ću ovak inaće..

#9: Autor/ica: lena,

Postano: 21:07 čet, 8. 2. 2007
—
Jel zna netko koja je složenost algoritma u 7.a) zadatku?

#10: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 21:22 čet, 8. 2. 2007
—

lena (napisa):

Jel zna netko koja je složenost algoritma u 7.a) zadatku?

"Protrcis" kroz sve parove tocaka, sto znaci iste dvije petlje kao kad nesto sortiras selection sortom, a to je kvadratno. Cool

#11: Autor/ica: lena,

Postano: 22:05 čet, 8. 2. 2007
—
Tnx. A kak bi išao pohlepni algoritam u istom zadatku?

#12: Autor/ica: FFF,

Postano: 1:18 pet, 9. 2. 2007
—
imate rjesenja ovih zadataka na http://web.studenti.math.hr/~tpetrina/
Smile

#13: Autor/ica: Mad Wilson,

Postano: 14:21 čet, 15. 2. 2007
—
OK. Mene i dalje muci 7c:

Kod:

Dan je prirodni broj N>=2 i koordinate N tocaka u ravnini (to jest, u X[0], X[1], ..., X[N] su zapisane x-koordinate tocaka, a u Y[0], Y[1], ..., Y[N] y-koordinate).

* * *

c) Koristeci divide-and-conquer tehniku, napisite egzaktni algoritam koji pronalazi trazene tocke u slozenosti boljoj od O(n^2).

Najbolja ideja do koje sam uspio doci je podjela na cetvorinke;

SLIKA1

Zadani skup podijelimo na 4 djela:

SLIKA2

pri cemu su sva 4 neprazna i dobro balansirana u smislu kardinaliteta (broja tocaka koje sadrze). Vec nakon 2 iteracije tog djeljenja dolazimo do ove situacije:

SLIKA3

Dakle, tocke u zelenom sektoru ne moramo usporedivati sa svim tockama iz polaznog skupa, vec samo sa tockama u okolnim sektorima. Kako okolnih sektora ima 9 (zeleni uracunat), a ukupno ima 16 sektora, tada smo (skoro pa) prepolovili broj usporedbi. Naravno postupak djeljenja na cetvorinke se nastavlja iterativno.

E sad, ijako to zvuci dobro (u teoriji), u biti nije, jer da bismo to implementirali (npr u C-u), moramo koristiti quad-tree, a problem nastaje sto je u nekoj visokoj iteraciji ponekad jako tesko utvrditi koji su susjedni sektori. Analogija za btree bi bila da je za neke cvorove ponekad jako tesko naci susjedne cvorove (one na istom nivou), jer je potrebno proci cijelo stablo da ih se nade...

Neka druga ideja...?

Zadnja promjena: Mad Wilson; 20:23 sub, 3. 3. 2007; ukupno mijenjano 1 put.

#14: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 14:29 čet, 15. 2. 2007
—
Ovako, na pamet: mozda bi pomoglo da ne inzistiras na izbalansiranosti, nego da stalno dijelis na pola? Think

Pripadnost sektoru ti je onda funkcija koja ovisi o koordinatama i dubini dijeljenja. Smile

Cini mi se da u prosjecnoj situaciji mozes racunati da ce ispasti izbalansirano. Cool

Forum@DeGiorgi -> Strukture podataka i algoritmi

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.