Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
Zvone Forumaš(ica)
Pridružen/a: 01. 07. 2003. (13:09:44) Postovi: (9D)16
|
Postano: 22:44 uto, 30. 1. 2007 Naslov: Objavljeni su zadaci za vjezbu za 2. kolokvij... |
|
|
...i mozete ih pronaci [url=http://web.math.hr/nastava/spa/kolokviji.php]ovdje[/url].
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 :))
-- 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.
...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 )
– 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.
|
|
[Vrh] |
|
Greda Forumaš(ica)
Pridružen/a: 01. 07. 2006. (14:00:26) Postovi: (44)16
Spol:
|
|
[Vrh] |
|
kika Forumaš(ica)
Pridružen/a: 11. 02. 2005. (09:36:12) Postovi: (188)16
|
|
[Vrh] |
|
Greda Forumaš(ica)
Pridružen/a: 01. 07. 2006. (14:00:26) Postovi: (44)16
Spol:
|
|
[Vrh] |
|
Debla Forumaš(ica)
Pridružen/a: 06. 12. 2005. (16:54:24) Postovi: (94)16
Spol:
|
|
[Vrh] |
|
andreao Forumaš(ica)
Pridružen/a: 10. 02. 2005. (12:08:18) Postovi: (46F)16
Lokacija: SK
|
|
[Vrh] |
|
mladac Forumaš(ica)
Pridružen/a: 24. 10. 2005. (22:46:14) Postovi: (4D5)16
Spol:
Lokacija: zg
|
|
[Vrh] |
|
Debla Forumaš(ica)
Pridružen/a: 06. 12. 2005. (16:54:24) Postovi: (94)16
Spol:
|
|
[Vrh] |
|
lena Forumaš(ica)
Pridružen/a: 09. 12. 2005. (21:21:59) Postovi: (4C)16
Spol:
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
lena Forumaš(ica)
Pridružen/a: 09. 12. 2005. (21:21:59) Postovi: (4C)16
Spol:
|
|
[Vrh] |
|
FFF Forumaš(ica)
Pridružen/a: 19. 11. 2006. (19:46:12) Postovi: (2A)16
|
|
[Vrh] |
|
Mad Wilson Forumaš(ica)
Pridružen/a: 29. 05. 2006. (22:51:14) Postovi: (121)16
|
Postano: 14:21 čet, 15. 2. 2007 Naslov: |
|
|
OK. Mene i dalje muci 7c:
[code:1]
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).
[/code:1]
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...?
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.
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
|
[Vrh] |
|
|