| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
charlotte
Forumaš(ica)
Pridružen/a: 25. 04. 2006. (14:30:51)
Postovi: (1E)16
|
 Postano: 11:26 čet, 23. 11. 2006 Naslov: 2 zad |
    |
|
|
Hej! Rjesavala sam zadatke koji su stavljeni za vjezbu za kolokvij i dosta toga mi nije jasno pa bi zamolila za pomoc kod ova 2 zad:
1. Zadano je binarno stablo u kojem svaki unutrasnji cvor ima oba djeteta. Neka je L1 suma duljina svih puteva od korijena do nekog lista, L2 suma duljina svih puteva od korijena do nekog unutrasnjeg cvora. Neka je n broj listova. Pokazite da tada vrijedi: L1=L2+2(n-1).
Probala sam to pokazati preko mat indukcije i ako uzmem za bazu stablo koje ima samo korijen dobivam L1=0 L2=0 n=0 i 0=-2?
Drugi zadatak je Napisite fju void dvoje(BTREE T) koja ispisuje oznake svih cvorova bin stabla koji imaju tocno dvoje djece.
Nisam sigurna jel to moze ovako:
void PREORDER (node i,BTREE T){
node c;
if(leftchild(i,T)!=lambda&&rightchild(i,T)!=lambda) printf("...",label(i,T));
c=leftchild(i,T);
while(c!=lambda){
PREORDER(c,T);
c=rightchild;
}
}
void dvoje(BTREE T){
node c;
c=root(T);
PREORDER(c,T);
}
Hvala na pomoci!
Hej! Rjesavala sam zadatke koji su stavljeni za vjezbu za kolokvij i dosta toga mi nije jasno pa bi zamolila za pomoc kod ova 2 zad:
1. Zadano je binarno stablo u kojem svaki unutrasnji cvor ima oba djeteta. Neka je L1 suma duljina svih puteva od korijena do nekog lista, L2 suma duljina svih puteva od korijena do nekog unutrasnjeg cvora. Neka je n broj listova. Pokazite da tada vrijedi: L1=L2+2(n-1).
Probala sam to pokazati preko mat indukcije i ako uzmem za bazu stablo koje ima samo korijen dobivam L1=0 L2=0 n=0 i 0=-2?
Drugi zadatak je Napisite fju void dvoje(BTREE T) koja ispisuje oznake svih cvorova bin stabla koji imaju tocno dvoje djece.
Nisam sigurna jel to moze ovako:
void PREORDER (node i,BTREE T){
node c;
if(leftchild(i,T)!=lambda&&rightchild(i,T)!=lambda) printf("...",label(i,T));
c=leftchild(i,T);
while(c!=lambda){
PREORDER(c,T);
c=rightchild;
}
}
void dvoje(BTREE T){
node c;
c=root(T);
PREORDER(c,T);
}
Hvala na pomoci!
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
GauSs_
Moderator
Pridružen/a: 28. 01. 2004. (21:01:17)
Postovi: (53C)16
Spol: 
Lokacija: 231
|
| Postano: 13:09 čet, 23. 11. 2006 Naslov: |
|
|
|
2. zad.
[code:1]
// preorder ispis
void dvoje(BTREE T){
if(T==NULL) return;
if( (LEFT_CHILD(T)!=lambda && RIGHT_CHILD(T)!=lambda ){
printf("%c ", LABEL(T));
}
dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T));
}
[/code:1]
2. zad.
| Kod: |
// preorder ispis
void dvoje(BTREE T){
if(T==NULL) return;
if( (LEFT_CHILD(T)!=lambda && RIGHT_CHILD(T)!=lambda ){
printf("%c ", LABEL(T));
}
dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T));
}
|
_________________ The purpose of life is to end
Prosle su godine kolokviji bili laksi, zar ne? |
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 13:32 čet, 23. 11. 2006 Naslov: |
|
|
|
Sitna izmjena, u smjeru ATP-izacije...
[code:1]// preorder ispis
void dvoje(BTREE T){
if(EMPTY(T)) return;
if( (LEFT_CHILD(T)!=LAMBDA && RIGHT_CHILD(T)!=LAMBDA ){
printf("%c ", LABEL(ROOT(T), T));
}
dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T));
}[/code:1]
;)
Prvi zadatak... ako stablo ima samo korijen, onda je on i list, pa je n=1 a ne nula. ;)
Sitna izmjena, u smjeru ATP-izacije...
| Kod: | // preorder ispis
void dvoje(BTREE T){
if(EMPTY(T)) return;
if( (LEFT_CHILD(T)!=LAMBDA && RIGHT_CHILD(T)!=LAMBDA ){
printf("%c ", LABEL(ROOT(T), T));
}
dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T));
} |
Prvi zadatak... ako stablo ima samo korijen, onda je on i list, pa je n=1 a ne nula.
_________________ 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.  |
|
| [Vrh] |
|
charlotte
Forumaš(ica)
Pridružen/a: 25. 04. 2006. (14:30:51)
Postovi: (1E)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 15:30 čet, 23. 11. 2006 Naslov: |
|
|
|
Pa, ti pozivas rekurzivni [tt]PREORDER()[/tt], u cemu je problem? :grebgreb: Samo ti fali drugi rekurzivni poziv. :D
I jos jedna stvar: ono sto smo Gauss i ja pisali
[code:1] dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T)); [/code:1]
nije dobro. Treba ici:
[code:1] BTREE sub;
...
LEFT_SUBTREE(ROOT(T), T, &sub); /* ili tako nekako; ne znam deklaraciju napamet */
dvoje(sub);
RIGHT_SUBTREE(ROOT(T), T, &sub); /* ili tako nekako; ne znam deklaraciju napamet */
dvoje(sub);[/code:1]
jer [tt]LEFT/RIGHT_CHILD()[/tt] vraca [tt]node[/tt] sto je samo u pointerskoj implementaciji isto sto i [tt]BTREE[/tt], ali generalno nije. :)
Pa, ti pozivas rekurzivni PREORDER(), u cemu je problem?  Samo ti fali drugi rekurzivni poziv. 
I jos jedna stvar: ono sto smo Gauss i ja pisali
| Kod: | dvoje(LEFT_CHILD(T));
dvoje(RIGHT_CHILD(T)); |
nije dobro. Treba ici:
| Kod: | BTREE sub;
...
LEFT_SUBTREE(ROOT(T), T, &sub); /* ili tako nekako; ne znam deklaraciju napamet */
dvoje(sub);
RIGHT_SUBTREE(ROOT(T), T, &sub); /* ili tako nekako; ne znam deklaraciju napamet */
dvoje(sub); |
jer LEFT/RIGHT_CHILD() vraca node sto je samo u pointerskoj implementaciji isto sto i BTREE, ali generalno nije. 
_________________ 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. |
|
| [Vrh] |
|
GauSs_
Moderator
Pridružen/a: 28. 01. 2004. (21:01:17)
Postovi: (53C)16
Spol:
Lokacija: 231
|
|
| [Vrh] |
|
vanja
Forumaš(ica)
Pridružen/a: 16. 02. 2006. (16:38:26)
Postovi: (9E)16
Spol: 
|
| Postano: 9:12 pet, 24. 11. 2006 Naslov: |
|
|
|
[quote="GauSs_"][code:1]....
if( (LEFT_CHILD(T)!=LAMBDA && RIGHT_CHILD(T)!=LAMBDA ){ ....
[/code:1][/quote]
zar LEFT_CHILD i RIGHT_CHILD ne primaju 2 parametra ???
prototipovi:
node LEFT_CHILD(node i, BTREE T)
node RIGHT_CHILD(node i, BTREE T)
da li bi bilo dobro ovako??
[code:1]// preorder ispis
void dvoje(BTREE T){
if(EMPTY(T)) return;
if( LEFT_CHILD(ROOT(T),T)!=LAMBDA && RIGHT_CHILD(ROOT(T),T)!=LAMBDA ){
printf("%c ", LABEL(ROOT(T), T));
}
BTREE sub;
LEFT_SUBTREE(T, &sub);
dvoje(sub);
RIGHT_SUBTREE(T, &sub);
dvoje(sub);
}[/code:1]
| GauSs_ (napisa): | | Kod: | ....
if( (LEFT_CHILD(T)!=LAMBDA && RIGHT_CHILD(T)!=LAMBDA ){ ....
|
|
zar LEFT_CHILD i RIGHT_CHILD ne primaju 2 parametra ???
prototipovi:
node LEFT_CHILD(node i, BTREE T)
node RIGHT_CHILD(node i, BTREE T)
da li bi bilo dobro ovako??
| Kod: | // preorder ispis
void dvoje(BTREE T){
if(EMPTY(T)) return;
if( LEFT_CHILD(ROOT(T),T)!=LAMBDA && RIGHT_CHILD(ROOT(T),T)!=LAMBDA ){
printf("%c ", LABEL(ROOT(T), T));
}
BTREE sub;
LEFT_SUBTREE(T, &sub);
dvoje(sub);
RIGHT_SUBTREE(T, &sub);
dvoje(sub);
} |
|
|
| [Vrh] |
|
GauSs_
Moderator
Pridružen/a: 28. 01. 2004. (21:01:17)
Postovi: (53C)16
Spol:
Lokacija: 231
|
|
| [Vrh] |
|
|
Hvala na pomoci! Jos me zanima jel moj program totalna katastrofa ili bi na kolokviju dobio neke bodove? Ti zadaci se moraju bas rjesavati preko rekurzija? 
