Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

1.kolokvij 2015/2016
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Oblikovanje i analiza algoritama
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
slonic~tonic
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 26. 10. 2011. (14:16:34)
Postovi: (84)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 4

PostPostano: 21:25 čet, 29. 10. 2015    Naslov: 1.kolokvij 2015/2016 Citirajte i odgovorite

http://web.math.pmf.unizg.hr/~singer/oaa/oaa_1415/2014_k1.pdf

Može rješenje 1.zadatka ?
http://web.math.pmf.unizg.hr/~singer/oaa/oaa_1415/2014_k1.pdf

Može rješenje 1.zadatka ?



_________________
Lakše je naučiti matematiku nego raditi bez nje.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:16 pet, 30. 10. 2015    Naslov: Citirajte i odgovorite

Uputa za a):[list][*] vanjska petlja se izvrsava za [tt]i = 1,2,...,n[/tt], dakle [b][tt]n[/tt] puta[/b];
[*] unutrasnja petlja se izvrsava za [tt]j = n, n/2, n/4,..., 1[/tt], sto znaci da za [tex]n[/tex] izmedju [tex]2^k[/tex] i [tex]2^{k+1}-1[/tex] imamo [tex]n = 2^k + r_1, 2^{k-1} + r_2, ..., 2^0[/tex], tj. [tex]k+1 = \lceil \lg(n+1) \rceil \approx \bf \lg n[/tex] [b]koraka[/b];
[*] Ukupno: pomnozi to dvoje jer je petlja u petlji.[/list:u]
Za b) ide slicno.
Uputa za a):
  • vanjska petlja se izvrsava za i = 1,2,...,n, dakle n puta;
  • unutrasnja petlja se izvrsava za j = n, n/2, n/4,..., 1, sto znaci da za [tex]n[/tex] izmedju [tex]2^k[/tex] i [tex]2^{k+1}-1[/tex] imamo [tex]n = 2^k + r_1, 2^{k-1} + r_2, ..., 2^0[/tex], tj. [tex]k+1 = \lceil \lg(n+1) \rceil \approx \bf \lg n[/tex] koraka;
  • Ukupno: pomnozi to dvoje jer je petlja u petlji.

Za b) ide slicno.



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Gost






PostPostano: 13:42 pet, 13. 11. 2015    Naslov: Gradivo 1. kolokvija Citirajte i odgovorite

Što sve ulazi u prvi kolokvij? Do kuda je profesor stigao s predavanjima?
Što sve ulazi u prvi kolokvij? Do kuda je profesor stigao s predavanjima?


[Vrh]
slonic~tonic
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 26. 10. 2011. (14:16:34)
Postovi: (84)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 4

PostPostano: 21:03 pet, 13. 11. 2015    Naslov: Citirajte i odgovorite

Zanima me slozenost 4.zadatka kolokvija: https://web.math.pmf.unizg.hr/~singer/oaa/oaa_0809/2008_k1.pdf

napisala sam algoritam: (koji samo vraća broj elemenata presjeka)
[code:1]int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
[/code:1]

Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??
Zanima me slozenost 4.zadatka kolokvija: https://web.math.pmf.unizg.hr/~singer/oaa/oaa_0809/2008_k1.pdf

napisala sam algoritam: (koji samo vraća broj elemenata presjeka)
Kod:
int presjek (a, b, n) {
   k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
   while(i<n & j<n) {
      if(a[i]==b[j]) { k++, i++, j++ }
      else if(a[i]>b[j]) j++
      i++
   }
   return k;
}


Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??



_________________
Lakše je naučiti matematiku nego raditi bez nje.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Gost






PostPostano: 15:00 sub, 21. 11. 2015    Naslov: Citirajte i odgovorite

jel se zna kad bi trebali biti rezultati?
jel se zna kad bi trebali biti rezultati?


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:38 sub, 21. 11. 2015    Naslov: Citirajte i odgovorite

[quote="slonic~tonic"][code:1]int presjek (a, b, n) {
k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
while(i<n & j<n) {
if(a[i]==b[j]) { k++, i++, j++ }
else if(a[i]>b[j]) j++
i++
}
return k;
}
[/code:1][/quote]

Cini mi se da bi [tt]i++[/tt] trebao biti u nekakvom [tt]else[/tt] bloku. (Ostalo ne komentiram, jer mi se cini da je to nekakav pseudo, a ne pravi C)

[quote="slonic~tonic"]Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??[/quote]

Obicno se broje aritmeticke operacije. Korak petlje, ovako kako je kod tebe napisano, ima izmedju jednog i cetiri poziva [tt]++[/tt], dakle izmedju [tex]O(n)[/tex] i [tex]O(4n)[/tex], sto je -- naravno -- jednako [tex]O(n)[/tex].

@Gost: Ne znam, ali vjerojatno ne jako brzo jer je profesor do kraja iduceg tjedna na sluzbenom putu.
slonic~tonic (napisa):
Kod:
int presjek (a, b, n) {
   k=0, i=0, j=0 // k je broj elemenata presjeka tj niza c
   while(i<n & j<n) {
      if(a[i]==b[j]) { k++, i++, j++ }
      else if(a[i]>b[j]) j++
      i++
   }
   return k;
}


Cini mi se da bi i++ trebao biti u nekakvom else bloku. (Ostalo ne komentiram, jer mi se cini da je to nekakav pseudo, a ne pravi C)

slonic~tonic (napisa):
Da li se za slozenost broje samo usporedbe a[i]==b[j] i a[i]>b[j] i onda je slozenost ovog algoritma O(2n) tj O(n) ??


Obicno se broje aritmeticke operacije. Korak petlje, ovako kako je kod tebe napisano, ima izmedju jednog i cetiri poziva ++, dakle izmedju [tex]O(n)[/tex] i [tex]O(4n)[/tex], sto je – naravno – jednako [tex]O(n)[/tex].

@Gost: Ne znam, ali vjerojatno ne jako brzo jer je profesor do kraja iduceg tjedna na sluzbenom putu.



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Oblikovanje i analiza algoritama Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan