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

2.kolokvij
WWW:
Idite na 1, 2  Sljedeće
Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Strukture podataka i algoritmi
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
angelika
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2011. (17:26:51)
Postovi: (5F)16
Sarma = la pohva - posuda
= 3 - 1

PostPostano: 15:46 čet, 17. 1. 2013    Naslov: 2.kolokvij Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2011/SPA%20-%202011%20-%20kolokvij2%20-%20zadaci.pdf

jel može neka ideja kako riješiti 1b?
http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2011/SPA%20-%202011%20-%20kolokvij2%20-%20zadaci.pdf

jel može neka ideja kako riješiti 1b?


[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: 16:07 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

Za svaki element domene [tt]d1[/tt] pozoves [tt]compute2()[/tt] i dobijes skup, nazovima ga [tt]s2[/tt], elemenata koji su s njim u relaciji. Zatim za svaki [tt]d2[/tt] iz skupa [tt]s2[/tt] opet pozoves [tt]compute2()[/tt] i dobijes skup, nazovima ga [tt]s3[/tt], elemenata koji su s njim u relaciji. Za svaki element [tt]d3[/tt] skupa [tt]s3[/tt] dodas [tt](d1,d3)[/tt] u relaciju.
Za svaki element domene d1 pozoves compute2() i dobijes skup, nazovima ga s2, elemenata koji su s njim u relaciji. Zatim za svaki d2 iz skupa s2 opet pozoves compute2() i dobijes skup, nazovima ga s3, elemenata koji su s njim u relaciji. Za svaki element d3 skupa s3 dodas (d1,d3) u relaciju.



_________________
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
mamba
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 09. 07. 2012. (17:11:16)
Postovi: (16)16
Sarma = la pohva - posuda
= 1 - 1

PostPostano: 16:17 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2011/SPA%20-%202011%20-%20kolokvij2%20-%20zadaci.pdf
a 4.?
http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2011/SPA%20-%202011%20-%20kolokvij2%20-%20zadaci.pdf
a 4.?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
angelika
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2011. (17:26:51)
Postovi: (5F)16
Sarma = la pohva - posuda
= 3 - 1

PostPostano: 18:05 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

hvala vsego :)
hvala vsego Smile


[Vrh]
Korisnički profil Pošaljite privatnu poruku
student_92
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 09. 2011. (16:31:46)
Postovi: (B9)16
Sarma = la pohva - posuda
10 = 16 - 6

PostPostano: 18:20 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

Može li netko kompetentan provjeriti ovaj kod (radi se o prvom zadatku iz 2012.)?

[code:1]int refleksivna(RELATION R) {
SET S;
int i;

for (i = 1; i <= N; ++i) {
MAKE_NULL_SET(&S);
COMPUTE2(R, I, &S);
if (!MEMBER(i, S)) return 0;
}

return 1;
}[/code:1]

EDIT: Uklonio sam b) zadatak jer sam u međuvremenu uvidio grešku, a budući da se nitko nije javio na to pitanje, nije problem. :)
Može li netko kompetentan provjeriti ovaj kod (radi se o prvom zadatku iz 2012.)?

Kod:
int refleksivna(RELATION R) {
    SET S;
    int i;

    for (i = 1; i <= N; ++i) {
        MAKE_NULL_SET(&S);
        COMPUTE2(R, I, &S);
        if (!MEMBER(i, S)) return 0;
    }

    return 1;
}


EDIT: Uklonio sam b) zadatak jer sam u međuvremenu uvidio grešku, a budući da se nitko nije javio na to pitanje, nije problem. Smile




Zadnja promjena: student_92; 22:23 čet, 17. 1. 2013; ukupno mijenjano 1 put.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
pedro
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 21. 10. 2010. (14:08:21)
Postovi: (19B)16
Sarma = la pohva - posuda
-22 = 16 - 38

PostPostano: 18:32 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

[quote="student_92"]Može li netko kompetentan provjeriti ovaj kod (radi se o prvom zadatku iz 2012.)?
U kodu je [b]napomena[/b] u jednoj liniji, a tiče se ovoga: s obzirom da nova relacija mora nuzno sadrzavati sve one "veze" koje su i u R, mislim da je taj red potreban. Jesam li u pravu ili ne? Ako ne, kako da inače postignem da sve ono što sadrži relacija R sadrži i moja nova relacija?

[code:1]int refleksivna(RELATION R) {
SET S;
int i;

for (i = 1; i <= N; ++i) {
MAKE_NULL_SET(&S);
COMPUTE2(R, I, &S);
if (!MEMBER(i, S)) return 0;
}

return 1;
}
[/code:1][/quote]

ne znam za ostalo ali mislim da bi ti trebalo ići doman2 i; a ne int i;

također set1 S, a ne SET S.

i mislim da bi MAKE_NULL_SET(&S); trebao ić izvan petlje

ja sam to ovako napravila:

[code:1]

int refleksivna (RELATION R)
{

set1 S1;
domain2 x;

MAKE_NULL(&S1);

for(x=1; x<=N;x++)
{
COMPUTE1(R, &S1, x);

if(!set1_MEMBER(x,S1))
return 0;

}

return 1;
}[/code:1]
student_92 (napisa):
Može li netko kompetentan provjeriti ovaj kod (radi se o prvom zadatku iz 2012.)?
U kodu je napomena u jednoj liniji, a tiče se ovoga: s obzirom da nova relacija mora nuzno sadrzavati sve one "veze" koje su i u R, mislim da je taj red potreban. Jesam li u pravu ili ne? Ako ne, kako da inače postignem da sve ono što sadrži relacija R sadrži i moja nova relacija?

Kod:
int refleksivna(RELATION R) {
    SET S;
    int i;

    for (i = 1; i <= N; ++i) {
        MAKE_NULL_SET(&S);
        COMPUTE2(R, I, &S);
        if (!MEMBER(i, S)) return 0;
    }

    return 1;
}


ne znam za ostalo ali mislim da bi ti trebalo ići doman2 i; a ne int i;

također set1 S, a ne SET S.

i mislim da bi MAKE_NULL_SET(&S); trebao ić izvan petlje

ja sam to ovako napravila:

Kod:


int refleksivna (RELATION R)
{

set1 S1;
domain2 x;

MAKE_NULL(&S1);

for(x=1; x<=N;x++)
{
COMPUTE1(R, &S1, x);

if(!set1_MEMBER(x,S1))
return 0;

}

return 1;
}


[Vrh]
Korisnički profil Pošaljite privatnu poruku
student_92
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 09. 2011. (16:31:46)
Postovi: (B9)16
Sarma = la pohva - posuda
10 = 16 - 6

PostPostano: 18:45 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

[quote="pedro"]
ne znam za ostalo ali mislim da bi ti trebalo ići doman2 i; a ne int i;
također set1 S, a ne SET S.
i mislim da bi MAKE_NULL_SET(&S); trebao ić izvan petlje
[/quote]

Ok. Ovo za tipove podataka, to i nije toliko bitno sada, važnije mi je ono što radi funkcija, ali svejedno hvala na napomeni.
Što se tiče MAKE_NULL_SET(), ipak mislim da to treba ići unutra jer svaki puta punimo skup nekim drugim elementima, ovisno o elementu [tex]i[/tex]. Osim ako f-ja COMPUTE() sama ne brine o tome. Mislim da u svakom slučaju nije greška da MAKE_NULL_SET() ide unutra. Čekamo treću/četvrtu itd. stranu da prokomentira.
pedro (napisa):

ne znam za ostalo ali mislim da bi ti trebalo ići doman2 i; a ne int i;
također set1 S, a ne SET S.
i mislim da bi MAKE_NULL_SET(&S); trebao ić izvan petlje


Ok. Ovo za tipove podataka, to i nije toliko bitno sada, važnije mi je ono što radi funkcija, ali svejedno hvala na napomeni.
Što se tiče MAKE_NULL_SET(), ipak mislim da to treba ići unutra jer svaki puta punimo skup nekim drugim elementima, ovisno o elementu [tex]i[/tex]. Osim ako f-ja COMPUTE() sama ne brine o tome. Mislim da u svakom slučaju nije greška da MAKE_NULL_SET() ide unutra. Čekamo treću/četvrtu itd. stranu da prokomentira.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
pedro
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 21. 10. 2010. (14:08:21)
Postovi: (19B)16
Sarma = la pohva - posuda
-22 = 16 - 38

PostPostano: 21:57 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

kako se "šeće" po ATP-u SET?
kako se "šeće" po ATP-u SET?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
kiara
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 15. 11. 2011. (23:22:57)
Postovi: (55)16
Sarma = la pohva - posuda
= 7 - 4

PostPostano: 22:53 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

Može li pomoć u vezi 4. zadatka sa prošlogodišnjeg kolokvija? Je li ga netko znao riješiti?
Može li pomoć u vezi 4. zadatka sa prošlogodišnjeg kolokvija? Je li ga netko znao riješiti?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
El_Loco
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 26. 05. 2012. (15:25:04)
Postovi: (31)16
Spol: muško
Sarma = la pohva - posuda
14 = 27 - 13

PostPostano: 23:43 čet, 17. 1. 2013    Naslov: Citirajte i odgovorite

[quote="pedro"]kako se "šeće" po ATP-u SET?[/quote]

uzmeš min/max i brišeš ga. to radiš dok set nije prazan
pedro (napisa):
kako se "šeće" po ATP-u SET?


uzmeš min/max i brišeš ga. to radiš dok set nije prazan


[Vrh]
Korisnički profil Pošaljite privatnu poruku
radivarig
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 29. 05. 2012. (21:36:08)
Postovi: (6)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 4:20 pet, 18. 1. 2013    Naslov: Citirajte i odgovorite

Nije bas na vrijeme odgovor s obzirom da je kolokvij za 5 sati, ali evo da pokusam (mozda netko ujutro škicne na forum nadajuci se odgovoru)

napravimo funkciju isRELATED
[code:1]int isRELATED(RELATION R, domain d1, domain d2){
set2 S2;
set_MAKE_NULL(&S2); //set_ ide ispred da razlikujemo MAKE_NULL za skup i relation
COMPUTE2(R,d1,&S2);
if(set_MEMBER(d2,S2)) return 1;
return 0;
}
[/code:1]

sad radimo funkciju REFLEKSIVNA
[code:1]int REFLEKSIVNA(RELATION R){
int i; //znamo da je elementtype domena d1 i d2 int
for(i=1;i<=N;i++) //usput N je globalna varijabla
if(!isRELATED(R, i, i)) return 0; //primjeti negaciju
return 1;
}[/code:1]

sretno![code:1]:)[/code:1]
Nije bas na vrijeme odgovor s obzirom da je kolokvij za 5 sati, ali evo da pokusam (mozda netko ujutro škicne na forum nadajuci se odgovoru)

napravimo funkciju isRELATED
Kod:
int isRELATED(RELATION R, domain d1, domain d2){
  set2 S2;
  set_MAKE_NULL(&S2); //set_ ide ispred da razlikujemo MAKE_NULL za skup i relation
  COMPUTE2(R,d1,&S2);
  if(set_MEMBER(d2,S2)) return 1;
  return 0;
}


sad radimo funkciju REFLEKSIVNA
Kod:
int REFLEKSIVNA(RELATION R){
  int i; //znamo da je elementtype domena d1 i d2 int
  for(i=1;i<=N;i++) //usput N je globalna varijabla
    if(!isRELATED(R, i, i)) return 0; //primjeti negaciju
  return 1;
}


sretno!
Kod:
:)


[Vrh]
Korisnički profil Pošaljite privatnu poruku
ivanaaaa
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 10. 2011. (19:36:26)
Postovi: (31)16
Sarma = la pohva - posuda
= 4 - 4

PostPostano: 12:14 ned, 3. 2. 2013    Naslov: Citirajte i odgovorite

jel bi mi htio neko objasniti 4b odavde : http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

trebam tu rekurzivnu formulu :)
jel bi mi htio neko objasniti 4b odavde : http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

trebam tu rekurzivnu formulu Smile


[Vrh]
Korisnički profil Pošaljite privatnu poruku
marsupial
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 09. 01. 2012. (22:46:33)
Postovi: (63)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
= 5 - 1

PostPostano: 22:21 sri, 11. 12. 2013    Naslov: Citirajte i odgovorite

da li netko zna riješiti prvi zadatak? Hvala :)

http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf
da li netko zna riješiti prvi zadatak? Hvala Smile

http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf


[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: 0:13 čet, 12. 12. 2013    Naslov: Citirajte i odgovorite

[quote="marsupial"]da li netko zna riješiti prvi zadatak? Hvala :)
http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf[/quote]

Poprilicno trivijalan zadatak. :?

a) Trci po svim elementima domene i prebroji za koliko njih je funkcija [tt]f[/tt] definirana.

[spoiler][code:1]int size(MAPPING f) {
domain i;
range r;
int cnt = 0;
for (i = 0; i <= n; i++)
if (MaCompute(f, i, *r)) cnt++;
return cnt;
}[/code:1][/spoiler]

b) Trci po elementima domene i gledaj one za koje je [tt]g[/tt] definirana. Ako za neki od tih elemenata [tt]f[/tt] nije definirana ili ima drugaciju vrijednost od funkcije [tt]g[/tt], vrati 0. Ako se to nikad ne desi, vrati 1.

[spoiler][code:1]int prosirenje(MAPPING f, MAPPING g) {
domain i;
range rf, rg;
for (i = 0; i <= n; i++)
if (MaCompute(g, i, *rg)) {
if (!MaCompute(f, i, *rf)) return 0;
if (rf != rg) return 0;
}
return 1;
}[/code:1][/spoiler]
marsupial (napisa):
da li netko zna riješiti prvi zadatak? Hvala Smile
http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf


Poprilicno trivijalan zadatak. Confused

a) Trci po svim elementima domene i prebroji za koliko njih je funkcija f definirana.

Spoiler [hidden; click to show]:


b) Trci po elementima domene i gledaj one za koje je g definirana. Ako za neki od tih elemenata f nije definirana ili ima drugaciju vrijednost od funkcije g, vrati 0. Ako se to nikad ne desi, vrati 1.

Spoiler [hidden; click to show]:



_________________
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
marsupial
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 09. 01. 2012. (22:46:33)
Postovi: (63)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
= 5 - 1

PostPostano: 0:36 pet, 13. 12. 2013    Naslov: Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/spa/files/zadaci_za_vjezbu_kolokvij2.pdf

4. zadatak pod d) i e) nemam ideje.. da li bi netko mogao raspisati?
http://web.math.pmf.unizg.hr/nastava/spa/files/zadaci_za_vjezbu_kolokvij2.pdf

4. zadatak pod d) i e) nemam ideje.. da li bi netko mogao raspisati?


[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: 3:57 pet, 13. 12. 2013    Naslov: Citirajte i odgovorite

d) Inicijaliziraj [tt]*gp[/tt] na prazni [tt]Mapping[/tt], pa trci po svim elementima [tt]x[/tt] domene od [tt]f[/tt] i za svaki izracunaj vrijednost [tt]r := f(x)[/tt]. Zatim provjeri je li definiran [tt]g(r)[/tt]. Ako je, to znaci da [tt]f[/tt] nije surjekcija, tj. inverz ne postoji, pa reinicijaliziraj [tt]g[/tt] i prekini izvrsavanje funkcije (vrati prazni [tt]Mapping[/tt]); inace postavi da je [tt]g(r) := x[/tt].

[spoiler][code:1]void inverz (Mapping f, Mapping *gp) {
char x, tmp, r;
MaMakeNull(gp);
for (x = 'a'; x <= 'z'; x++)
if (MaCompute(f, x, &r)) {
if (MaCompute(*gp, r, &tmp)) {
/* Vec imamo definiran g(r), pa f nije surjekcija */
MaMakeNull(gp);
return;
}
MaAssign(gp, r, x);
}
}[/code:1][/spoiler]

e) Inicijaliziraj [tt]*hp[/tt], pa trci po domeni (opet elemente oznacavam s [tt]x[/tt]). Za svaki [tt]x[/tt] izracunaj [tt]rf := f(x)[/tt], a zatim izracunaj i [tt]r := g(rf)[/tt]. Nakon toga definiraj [tt]h(x) := r[/tt].
Ako [tt]f(x)[/tt] nije definiran, preskaces taj [tt]x[/tt].
Ako [tt]g(rf)[/tt] nije definiran, onda kompoziciju nije moguce definirati. U zadatku taj slucaj nije pokriven, pa mozes birati sto napraviti. Meni se cini najcisce, kao pod d), reinicijalizirati [tt]*hp[/tt] i prekinuti funkciju (dakle, vratiti prazni [tt]Mapping[/tt]).

Kod prepustam tebi za zabavu. U osnovi je jako slican ovom pod d).
d) Inicijaliziraj *gp na prazni Mapping, pa trci po svim elementima x domene od f i za svaki izracunaj vrijednost r := f(x). Zatim provjeri je li definiran g(r). Ako je, to znaci da f nije surjekcija, tj. inverz ne postoji, pa reinicijaliziraj g i prekini izvrsavanje funkcije (vrati prazni Mapping); inace postavi da je g(r) := x.

Spoiler [hidden; click to show]:


e) Inicijaliziraj *hp, pa trci po domeni (opet elemente oznacavam s x). Za svaki x izracunaj rf := f(x), a zatim izracunaj i r := g(rf). Nakon toga definiraj h(x) := r.
Ako f(x) nije definiran, preskaces taj x.
Ako g(rf) nije definiran, onda kompoziciju nije moguce definirati. U zadatku taj slucaj nije pokriven, pa mozes birati sto napraviti. Meni se cini najcisce, kao pod d), reinicijalizirati *hp i prekinuti funkciju (dakle, vratiti prazni Mapping).

Kod prepustam tebi za zabavu. U osnovi je jako slican ovom pod d).



_________________
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
marsupial
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 09. 01. 2012. (22:46:33)
Postovi: (63)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
= 5 - 1

PostPostano: 14:04 sub, 18. 1. 2014    Naslov: Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

Da li je netko pokušao/napisao 4. zadatak?

[size=9][color=#999999]Added after 26 minutes:[/color][/size]


Rješenje 2. zadatka iz http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

da li je korektno?

funkcija broj_potomaka mi računa za svaki čvor broj njegovih potomaka
funkcija najveci mi vraća čvor brata koji ima najviše potomaka
funkcijom preorder zapravo šećemo po stablu i tako koristeći prethodne dvije funkcije mi ispisuje svu braću koji imaju više potomaka od preostale braće
-i plodni mi zapravo ''vrti'' preorder, što je zapravo sve moglo biti ukomponirano u jednu funkciju

[code:1]

int broj_potomaka(node n, Tree T){

int brojac =0;

if(n== LAMBDA) return 0;

if(TrFirstChild(n, T)!=LAMBDA){
brojac++;

c=TrFirstChild(n,T);

while(TrNextSibling(c, T)!=LAMBDA) brojac ++;
}

return brojac;
}

node najveci( node n, Tree T){

node c;
int m= broj_potomaka(n,T);

while(TrNextSibling(n,T)!=LAMBDA){

if(broj_potomaka(TrNextSibling(n,T),T)> m){

m=broj_potomaka(TrNextSibling(n,T),T);
n=TrNextSibling(n,T);
c=n;
}
}

return c;
}

void preorder(node n, Tree T){

node c;
printf("%d", TrLabel(najveci(n,T),T));

c=TrFirstChild(n,T);

while(c!=LAMBDA){
preorder(c,T);
c=TrNextSibling(c,T);
}

}

void plodni(Tree T){
n=TrRoot(T);
preorder(n,T);
}

[/code:1]
http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

Da li je netko pokušao/napisao 4. zadatak?

Added after 26 minutes:


Rješenje 2. zadatka iz http://web.math.pmf.unizg.hr/nastava/spa/kolokviji/2012/SPA%20-%202012%20-%20kolokvij2%20-%20zadaci.pdf

da li je korektno?

funkcija broj_potomaka mi računa za svaki čvor broj njegovih potomaka
funkcija najveci mi vraća čvor brata koji ima najviše potomaka
funkcijom preorder zapravo šećemo po stablu i tako koristeći prethodne dvije funkcije mi ispisuje svu braću koji imaju više potomaka od preostale braće
-i plodni mi zapravo ''vrti'' preorder, što je zapravo sve moglo biti ukomponirano u jednu funkciju

Kod:


int broj_potomaka(node n, Tree T){

   int brojac =0;

   if(n== LAMBDA)  return 0;

   if(TrFirstChild(n, T)!=LAMBDA){
     brojac++;

     c=TrFirstChild(n,T);

     while(TrNextSibling(c, T)!=LAMBDA) brojac ++;
   }

   return brojac;
}

node najveci( node n, Tree T){

   node c;
   int m= broj_potomaka(n,T);

   while(TrNextSibling(n,T)!=LAMBDA){

     if(broj_potomaka(TrNextSibling(n,T),T)> m){

        m=broj_potomaka(TrNextSibling(n,T),T);
        n=TrNextSibling(n,T);
        c=n;
     }
   }

return c;
}

void preorder(node n, Tree T){

   node c;
   printf("%d", TrLabel(najveci(n,T),T));

   c=TrFirstChild(n,T);

   while(c!=LAMBDA){
     preorder(c,T);
     c=TrNextSibling(c,T);
   }

}

void plodni(Tree T){
   n=TrRoot(T);
   preorder(n,T);
}



[Vrh]
Korisnički profil Pošaljite privatnu poruku
nuclear
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 11. 2011. (17:40:12)
Postovi: (74)16
Spol: žensko
Sarma = la pohva - posuda
10 = 20 - 10

PostPostano: 13:43 uto, 28. 1. 2014    Naslov: Citirajte i odgovorite

Postoji li neka dobra duša kojoj bi mogla poslati svoje kodove da mi pregleda i kaže jesu li u redu? (Ne rješavam više zadatke u code blocksu zato što mi oduzima previše vremena na traženje sitnih grešaka i pisanju implementacija i ostalog, a samo treba riješiti jednu funkciju.) :)
Postoji li neka dobra duša kojoj bi mogla poslati svoje kodove da mi pregleda i kaže jesu li u redu? (Ne rješavam više zadatke u code blocksu zato što mi oduzima previše vremena na traženje sitnih grešaka i pisanju implementacija i ostalog, a samo treba riješiti jednu funkciju.) Smile


[Vrh]
Korisnički profil Pošaljite privatnu poruku
nuclear
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 11. 2011. (17:40:12)
Postovi: (74)16
Spol: žensko
Sarma = la pohva - posuda
10 = 20 - 10

PostPostano: 18:02 sri, 29. 1. 2014    Naslov: Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/spa/files/zadaci_za_vjezbu_kolokvij2.pdf

Pitanje za 2. zad: znači li to da radim "obratno od hrpe", da je u čvoru tada najveći element i da su djeca roditelja čvora manja od roditelja? Ako ne, na šta se onda mislilo?

Pitanje za 3. zad: mogu li se ponavljati elementi? recimo da sortirano bude oblika: 2 3 5 5 7 7 8 9?
http://web.math.pmf.unizg.hr/nastava/spa/files/zadaci_za_vjezbu_kolokvij2.pdf

Pitanje za 2. zad: znači li to da radim "obratno od hrpe", da je u čvoru tada najveći element i da su djeca roditelja čvora manja od roditelja? Ako ne, na šta se onda mislilo?

Pitanje za 3. zad: mogu li se ponavljati elementi? recimo da sortirano bude oblika: 2 3 5 5 7 7 8 9?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
mew_17
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 07. 2011. (16:38:05)
Postovi: (29)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
39 = 39 - 0

PostPostano: 15:54 ned, 1. 2. 2015    Naslov: Citirajte i odgovorite

Može li netko riješiti ovaj zadatak?

Mirko treba izracunati zbroj a[0]+a[1]+...+a[n-1]. On to radi tako da odabere neka dva susjedna broja u sumi, te ih zamjeni njihovim zbrojem. Da bi Mirko izracunao zbroj x + y, treba mu max{x, y} sekundi. Kojim redom Mirko treba zbrajati brojeve tako da izracuna sumu u najkracem mogucem vremenu? Na primjer, ako treba izracunati 1 + 4 + 2 + 1, Mirko moze prvo zbrojiti 2 + 1 za 2 sekunde; preostaje mu izracunati
1 + 4 + 3; zatim moze izracunati 1 + 4 za 4 sekunde; preostaje mu izracunati 5 + 3 za sto mu treba 5 sekundi { dakle, ukupno je utrosio 11 sekundi.

(a) Opisite rijecima neki pohlepni algoritam i objasnite zasto je pohlepan. Dokazite da algoritam uvijek nade minimalan broj sekundi ili konstruirajte kontraprimjer.

(b) Neka je M(p; q) minimalan broj sekundi da bi se izracunao zbroj a[p]+a[p+1]+...+a[q]. Napisite rekurzivnu formulu za M(p; q). Zatim, koristeci dinamicko programiranje, napisite funkciju int M(int p, int q) koja pozvana sa M(0, n-1) vraca minimalan broj sekundi za izracunavanje zbroja a[0]+a[1]+...+a[n-1]. Pretpostavite da je a globalna varijabla.
Može li netko riješiti ovaj zadatak?

Mirko treba izracunati zbroj a[0]+a[1]+...+a[n-1]. On to radi tako da odabere neka dva susjedna broja u sumi, te ih zamjeni njihovim zbrojem. Da bi Mirko izracunao zbroj x + y, treba mu max{x, y} sekundi. Kojim redom Mirko treba zbrajati brojeve tako da izracuna sumu u najkracem mogucem vremenu? Na primjer, ako treba izracunati 1 + 4 + 2 + 1, Mirko moze prvo zbrojiti 2 + 1 za 2 sekunde; preostaje mu izracunati
1 + 4 + 3; zatim moze izracunati 1 + 4 za 4 sekunde; preostaje mu izracunati 5 + 3 za sto mu treba 5 sekundi { dakle, ukupno je utrosio 11 sekundi.

(a) Opisite rijecima neki pohlepni algoritam i objasnite zasto je pohlepan. Dokazite da algoritam uvijek nade minimalan broj sekundi ili konstruirajte kontraprimjer.

(b) Neka je M(p; q) minimalan broj sekundi da bi se izracunao zbroj a[p]+a[p+1]+...+a[q]. Napisite rekurzivnu formulu za M(p; q). Zatim, koristeci dinamicko programiranje, napisite funkciju int M(int p, int q) koja pozvana sa M(0, n-1) vraca minimalan broj sekundi za izracunavanje zbroja a[0]+a[1]+...+a[n-1]. Pretpostavite da je a globalna varijabla.


[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 2. godine -> Strukture podataka i algoritmi Vremenska zona: GMT + 01:00.
Idite na 1, 2  Sljedeće
Stranica 1 / 2.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne 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