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

Identična podstabla
WWW:

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


Pridružen/a: 08. 12. 2010. (13:11:02)
Postovi: (21)16
Sarma = la pohva - posuda
2 = 2 - 0
PostPostano: 20:16 sri, 14. 11. 2012    Naslov: Identična podstabla Citirajte i odgovorite
Zapela sam kod idućeg zadatka:

[i]Napisite funkciju s prototipom int listovi(BTREE T, int k) koja vraca 1 ako u stablu T postoje dva identicna
podstabla koja imaju tocno k listova, a 0 u protivnom. Podstabla su identicna ako im se podudaraju i raspored
i oznake cvorova.
Funkcija treba biti neovisna o implementaciji atp BTREE; smijete de nirati i dodatne pomocne funkcije. Nije
dozvoljeno koristenje funkcija LEFT_SUBTREE i RIGHT_SUBTREE.[/i]

Naime, nemam neku pametnu ideju kako bi provjerila jesu li dva podstabla identična, pa ako ima netko tko zna bila bih jako zahvalna. :)
Zapela sam kod idućeg zadatka:

Napisite funkciju s prototipom int listovi(BTREE T, int k) koja vraca 1 ako u stablu T postoje dva identicna
podstabla koja imaju tocno k listova, a 0 u protivnom. Podstabla su identicna ako im se podudaraju i raspored
i oznake cvorova.
Funkcija treba biti neovisna o implementaciji atp BTREE; smijete de nirati i dodatne pomocne funkcije. Nije
dozvoljeno koristenje funkcija LEFT_SUBTREE i RIGHT_SUBTREE.

Naime, nemam neku pametnu ideju kako bi provjerila jesu li dva podstabla identična, pa ako ima netko tko zna bila bih jako zahvalna. Smile


[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
0 = 1 - 1
PostPostano: 23:11 sri, 14. 11. 2012    Naslov: Citirajte i odgovorite
Jel se u tom zadatku misli na identična podstabla istog čvora ili bilo koja dva čvora u stablu?
Ako ovo drugo, kako da tada za svaka dva čvora provjerim zadovoljavaju li tražene uvjete?
Jel se u tom zadatku misli na identična podstabla istog čvora ili bilo koja dva čvora u stablu?
Ako ovo drugo, kako da tada za svaka dva čvora provjerim zadovoljavaju li tražene uvjete?


[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: 17:26 čet, 15. 11. 2012    Naslov: Citirajte i odgovorite
evo moje rješenje, djeluje mi točno...

ideja je proći kroz stablo i sve čvorove koji imaju k listova zapamtiti u niz.
zatim taj niz uspoređivati fjom usporedi, koja vrati 0 ako su jednaki, a nešto veće od 0 ako nisu.

[code:1]int broj_listova( node i, BTREE T )
{
if( i == LAMBDA )
return 0;
if( LEFT_CHILD(i,T) == LAMBDA && RIGHT_CHILD(i,T) == LAMBDA )
return 1;
return broj_listova(LEFT_CHILD(i,T),T) + broj_listova(RIGHT_CHILD(i,T),T);
}

void prodji_i_zapamti( node i, BTREE T, node* niz, int* duljina, int k )
{
if( i == LAMBDA )
return;
if( broj_listova(i,T) == k )
{
niz[*duljina] = i;
(*duljina)++;
}
prodji_i_zapamti(LEFT_CHILD(i,T),T,niz,duljina,k);
prodji_i_zapamti(RIGHT_CHILD(i,T),T,niz,duljina,k);
}

int usporedi( node a, node b, BTREE T )
{
if( a == LAMBDA && b == LAMBDA )
return 0;
if( LABEL(a,T) != LABEL(b,T) )
return 1;
return usporedi(LEFT_CHILD(a,T),LEFT_CHILD(b,T),T) + usporedi(RIGHT_CHILD(a,T),RIGHT_CHILD(b,T),T);
}

int listovi(BTREE T, int k)
{
node a[MAX];
int n, i, j;
prodji_i_zapamti(ROOT(T),T,a,&n,k);
for( i = 0; i < n-1; i++ )
for( j = i+1; j < n; j++ )
if( usporedi(a[i],a[j],T) )
return 1;
return 0;
}[/code:1]
evo moje rješenje, djeluje mi točno...

ideja je proći kroz stablo i sve čvorove koji imaju k listova zapamtiti u niz.
zatim taj niz uspoređivati fjom usporedi, koja vrati 0 ako su jednaki, a nešto veće od 0 ako nisu.

Kod:
int broj_listova( node i, BTREE T )
{
    if( i == LAMBDA )
        return 0;
    if( LEFT_CHILD(i,T) == LAMBDA && RIGHT_CHILD(i,T) == LAMBDA )
        return 1;
    return broj_listova(LEFT_CHILD(i,T),T) + broj_listova(RIGHT_CHILD(i,T),T);
}

void prodji_i_zapamti( node i, BTREE T, node* niz, int* duljina, int k )
{
    if( i == LAMBDA )
        return;
    if( broj_listova(i,T) == k )
    {
        niz[*duljina] = i;
        (*duljina)++;
    }
    prodji_i_zapamti(LEFT_CHILD(i,T),T,niz,duljina,k);
    prodji_i_zapamti(RIGHT_CHILD(i,T),T,niz,duljina,k);
}

int usporedi( node a, node b, BTREE T )
{
    if( a == LAMBDA && b == LAMBDA )
        return 0;
    if( LABEL(a,T) != LABEL(b,T) )
        return 1;
    return usporedi(LEFT_CHILD(a,T),LEFT_CHILD(b,T),T) + usporedi(RIGHT_CHILD(a,T),RIGHT_CHILD(b,T),T);
}

int listovi(BTREE T, int k)
{
    node a[MAX];
    int n, i, j;
    prodji_i_zapamti(ROOT(T),T,a,&n,k);
    for( i = 0; i < n-1; i++ )
        for( j = i+1; j < n; j++ )
            if( usporedi(a[i],a[j],T) )
                return 1;
    return 0;
}


[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.
Stranica 1 / 1.

 
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