Strukture za sve

shredder · **Poslato:** 04.07.2006. 10:43:12

@ scully

Ima uradjen hashing na forumu. Pogledaj na prethodnoj strani mislim da je kliford dao link gdje su prevedeni oni kodovi u C-u.

Ako je duzina niza 102, zasto bi trebalo % 103?

Scully · **Poslato:** 04.07.2006. 11:01:28

shredder je napisao:

@ scully

Ako je duzina niza 102, zasto bi trebalo % 103?

Zato sto kaze: "Najbolji rezultati, tj. najmanji broj kolizija, se dobija kada je M prost broj nesto veci od raspolozivog adresnog prostora.".

shredder · **Poslato:** 04.07.2006. 11:41:10

ali ti ne treba da napises kako se rjesava kolizija, nego da pretrazis niz kod koga je kolizija rjesena na neki od ona dva nacina.

Scully · **Poslato:** 04.07.2006. 12:55:36

pa kada trazis na kom je mestu 'isto' je kao da ga smestas na to mesto... :zbun:

Paf · **Poslato:** 05.07.2006. 14:09:15

Scully je napisao:

shredder je napisao:

@ scully

Ako je duzina niza 102, zasto bi trebalo % 103?

Zato sto kaze: "Najbolji rezultati, tj. najmanji broj kolizija, se dobija kada je M prost broj nesto veci od raspolozivog adresnog prostora.".

Opustrno mozes pisati kako god zelis, u principu kad to implementiras preko niza, tebi je prvi indeks 0, a poslednji 101, pa kad podelis sa 102 opet dobijas ostatak koji je pogodan za resavanje kolizije

Punoglavac · **Poslato:** 06.07.2006. 08:46:26

[quote="Punoglavac"]Pozdrav, imam dva pitanja i jedno obavestenje...

Obavestenje je da ce vam doci (99%) jedan od sledecih zadataka...
20. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava olančavanjem.

24. Napišite algoritam za pretraživanje transformacijom ključa u adresu u kome se problem kolizije rešava otvorenim adresiranjem.

Samo da se zna da niste htjeli da me poslusate, a reko sam vam da ce vam to doci...

User · **Poslato:** 11.07.2006. 12:25:12

Napravio sam skriptu za ovaj predmet, nalazi se:

OVDE

Darth Neman · **Poslato:** 28.08.2006. 22:34:30

Aplet za AVL stabla
Aplet za B stabla

Prof dr Kadzija · **Poslato:** 29.08.2006. 12:24:04

Evo mojih zadataka iz juna (nadam se da ce to nekom koristiti):

IV grupa

1. Navedite slucaj kada interpolaciono pretrazivanje ima bolje performanse od binarnog.

2. Dva binarna stabla su identicna ako su ista po strukturi i sadrzaju, tj. oba korena imaju isti sadrzaj i njihova odgovarajuca podstabla su identicna. Napisati funkciju koja ce proveriti da li su dva binarna stabla identicna.

3. Pokazati postupak formiranja AVL stabla kada se u stablo prikazano na slici ubacuje sledeci niz kljuceva: 70, 55, 150, 100.

4. Napisati funkciju "izbaci" nad stakom celih brojeva koji je implementiran kao dvostruko spregnuta lista.

5. napisati funkciju koja implementira pretrazivanje niza celih brojeva koristeci transformaciju kljuca u adresu. Dimenzija niza je 102, a za funkciju transformacije koristiti moduo (ostatak celobrojnog deljenja). Problem kolizije se resava metodom olancavanja.

6. Dato je B* stablo kod koga je maksimalni broj kljuceva u stablu dva:

a) Ubaciti u dato stablo kljuceve 25, 100, 180, 120, 150.
b) Izbaciti iz datog stabla kljuceve 200, 50, 30.

7. Napisati proceduru koja stampa sadrzaj svih cvorova binarnog stabla (nije BST) na putanji od korena do cvora koji ima najmanju vrednost u stablu.

Kai · **Poslato:** 29.08.2006. 15:41:46

Jel može neko da mi uradi 3. i 6. zadatak?
Gledao sam skriptu i mislio sam da sam dobro ukapirao ali očigledno nisam pošto nisam položio u junu.
:udri:

donald · **Poslato:** 29.08.2006. 17:09:43

Sto se tice AVL stabala pogledaj onaj link za AVL aplet (sto je Darth Neman) postavio. Bice ti mnogo od pomoci, a i lakse ces ukapirati. A za b* imas na "novijoj" skripti na sajtu, pa ako nesto ne bude jasno, pitaj.

A da li neko moze da postavi resenje (ko je inace tacno uradio u junu) za sledeci zadatak:

- Napisati funkciju koja implementira pretraživanje niza celih brojeva koristeći transformaciju ključa u adresu. Dimenzija niza je 102, a za funkciju transformacije koristiti moduo (ostatak od celobrojnog deljenja). Problem kolizije se rešava metodom otvorenog adresiranja.

Darth Neman · **Poslato:** 29.08.2006. 19:11:05

^

Kod:

public static int otvAdr(int[] niz, int kljuc){
   int j = kljuc%niz.length;
   if (niz[j] == kljuc)
      return niz[j];
      else {
        j +=1;
        for (j; j<niz.length; j++){
         if (niz[j] == kljuc)
            return niz[j];
        } else
         return -1; //element nije nadjen
      }
}

baneizalfe · **Poslato:** 29.08.2006. 20:57:48

Ja sam ,kao, probao ovaj sa B stablom...

Kod:

Dato je B stablo kod koga je maksimalni broj kljuceva u stablu dva:


                 (  150  )
                 /        \       
       ( 25  45 )       ( 180 )
       

Ubaciti u dato stablo kljuceve 15, 80, 140. 

+15
          (  150  )         ( 25  150 )            
         /        \           <=>        /   |   \               
( 15  25  45 )       ( 180 )     ( 15 )   ( 45 )  ( 180 )
    
    
+50

          ( 25 150 )   
    /    |     \
( 15 )   ( 45  50 )  ( 180 )


+250

   ( 25 150 )
   /    |   \
( 15 )  ( 45  50 )  ( 180  250 )

Ko zna dal je ovo tacno? E sad za izbacivanje nemam pojma dal se to odnosi na stablo sam sad dobio il na pocetno, jer u tekstu lepo pise DATO stablo

Darth Neman · **Poslato:** 29.08.2006. 22:17:55

^Pa ti kucas jedno u postavci a drugo ubacujes!

Za 80 je isto kao sto si odradio za 50...
Tacno je i za 250... Ali si ti rekao u postavci da treba da ubacis 140!

za 140 ide ovako (dva puta se cepa cvor):

Kod:

                   (80)
                 /       \
              (25)        (150)
            /     \      /     \
         (15)    (45) (140)    (180)

A za izbacivanje ako ti je napisano "dato" ja bi radio sa pocetnim... Da mi je pisalo "dobijeno" radio bi na onom koje sam dobio...

ElektroPoslasticar · **Poslato:** 29.08.2006. 23:18:13

Citiraj:

7. Napisati proceduru koja stampa sadrzaj svih cvorova binarnog stabla (nije BST) na putanji od korena do cvora koji ima najmanju vrednost u stablu.

.. i moj skromni doprinos

Mozda nekom bude zanimljivo, ne znam da li to moze krace da se uradi

Kod:

        // Nalazi TNode sa najmanjom vrednoscu
        public static TNode FindMin(TNode aRoot)
        {
            TNode minNode,tmpNode;
            if (aRoot == null) return null;

            minNode = aRoot;
          
            // Levo podstablo..
            tmpNode = FindMin(aRoot.left);
            if (tmpNode != null)
            if (minNode.data > tmpNode.data)
                minNode = tmpNode;

            // Desno podstablo..
            tmpNode = FindMin(aRoot.right);
            if (tmpNode != null)
            if (minNode.data > tmpNode.data)
                minNode = tmpNode;

            return minNode;
        }

        // Da li aRoot sadrzi node kao podcvor
        public static bool ImaPodCvor(TNode aRoot, TNode node)
        {            
            if (aRoot == null) return false;
            if (aRoot == node) return true;
            return false || ImaPodCvor(aRoot.left, node) || ImaPodCvor(aRoot.right, node);
        }

        // Stampa putanju do najmanjeg
        // Proverava da li se node sa najmanjom vrednoscu
        // nalazi u levom ili desnom podstablu
        // i tako se 'krece' po stablu
        public static void PutanjaDoNajmanjeg(TNode aRoot)
        {
            TNode node, tmpNode;
            node = FindMin(aRoot);
            tmpNode = aRoot;
            
            while (tmpNode != node)
            {
                Console.Write(tmpNode.data);
                if (ImaPodCvor(tmpNode.left, node))
                    tmpNode = tmpNode.left;
                else                
                    tmpNode = tmpNode.right;                
            }
            Console.Write(tmpNode.data);
        }

Paf · **Poslato:** 30.08.2006. 02:17:16

Pa dobro, kad je rec o ispisivanju cvorova, evo zadatka koji je meni dosao u junu:

Citiraj:

Napisati f-ju koja ispisuje vrednosti cvorova na putu od korena do cvora sa najvecom vrednoscu (nije BST-stablo).

Ovo je u principu suprotan zadatak u odnosu na ovaj koji je resio ElektroPoslasticar, a evo i resenja:

Kod:

public static void stampaj1(TreeNode node)
   {
      if(node!=null)
      {
         System.out.print(node.Data+" ");
         if(node.Data<Math.max(najveci(node.Left),
               najveci(node.Right)))
         {
            if(najveci(node.Left)>najveci(node.Right))
               stampaj1(node.Left);
            else stampaj1(node.Right);
         }else
         System.out.println("Kraj");
      }else
      System.err.println("Greska!");
   }
   
   public static int najveci(TreeNode node)
   {
      if(node==null)
         return Integer.MIN_VALUE;
      else 
      {
         int levi = Math.max(node.Data,najveci(node.Left));
         int desni = Math.max(node.Data,najveci(node.Right));
         return (Math.max(levi,desni));
      }
   }

baneizalfe · **Poslato:** 30.08.2006. 03:07:19

Citiraj:

^Pa ti kucas jedno u postavci a drugo ubacujes!
Za 80 je isto kao sto si odradio za 50...
Tacno je i za 250... Ali si ti rekao u postavci da treba da ubacis 140!
za 140 ide ovako (dva puta se cepa cvor):
Code:
(80)
/ \
(25) (150)
/ \ / \
(15) (45) (140) (180)

A za izbacivanje ako ti je napisano "dato" ja bi radio sa pocetnim... Da mi je pisalo "dobijeno" radio bi na onom koje sam dobio...

AAA moja pogreska. POstavka za jednu grupu, rad za drugu :lol:

Aj sad neko da uradi izbacivanje... I za dato i za dobijeno stablo...

Kai · **Poslato:** 30.08.2006. 03:59:04

Imate na temi u trećoj godini link ka zip fajlu, sa uputstvom. Ima dosta kodova, da ne ponavljam već istu priču. Pogledajte tamo.
Pozdrav

nikornla · **Poslato:** 30.08.2006. 04:22:35

Prof dr Kadzija je napisao:

Evo mojih zadataka iz juna (nadam se da ce to nekom koristiti):

IV grupa

3. Pokazati postupak formiranja AVL stabla kada se u stablo prikazano na slici ubacuje sledeci niz kljuceva: 70, 55, 150, 100.

6. Dato je B* stablo kod koga je maksimalni broj kljuceva u stablu dva:

a) Ubaciti u dato stablo kljuceve 25, 100, 180, 120, 150.
b) Izbaciti iz datog stabla kljuceve 200, 50, 30.

E koji sam ja maler. Taman lepo uradio detaljno oba zadatka u svesci sa namerom da slikam mobom, prebacim na komp i okacim resenja na net, kad previdim da mozda necu moci da prebacim slike (sto je i bio slucaj) zato sto mi komp lose stoji sa zdravljem u posednje vreme, a sa druge starne mi je previse mucno da crtam u paint-u, tako da cu ovde samo ukratko da obrazlozim resenja. U slucaju da negde gresim, nek me neko ispravi.

Kod:

3.

   (40)               (40)              (40)               (70)
  /   \   +70 =      /    \    +55=     /   \     +150=    /  \
(20) (90)         (20)    (90)      (20)    (70)        (40)   (90)
                         /                  /  \         / \      \
                       (70)               (55) (90)   (20) (55)   (150)



            (70)
+100=      /    \
       (40)      (100)
       / \        /  \
   (20)  (55) (90)    (150)


6.
a) 
        (130)              (50)                    (50,130)
        /  \     +25=      /  \         +100=      /   |   \
  (30,50)   (200)    (25,30)   (130,200)     (25,30) (100)  (200)


            (50,130)                      (50 ,130) 
+180=      /   |    \        +120=       /    |    \
     (25,30) (100)  (180,200)     (25,30) (100,120) (180,200)

  
                  (  130  )
                /          \
+150=    ( 50 )             ( 180 ) 
         /   \              /      \
   (25,30)   (100,120)  (150)       (200)

b)

        (130)             (50)                 
        /   \    -200=    /   \    -50= (30,130) -30= (130)
  (30,50)   (200)     (30)    (130)         

Uhhhhh... to je to. Ako sam nesto pogresio, nek me ispravi neko.

donald · **Poslato:** 30.08.2006. 12:05:20

A da li na ispitu mozemo da koristimo npr. metodu Math.max() ili Math.min() kao sto je to Paf koristio u svom kodu?

Darth Neman · **Poslato:** 30.08.2006. 13:17:05

^ Naravno da mozes... To su java-ine metode i klase...

Paf · **Poslato:** 30.08.2006. 14:29:51

U principu najbitnija ti je logika resavanja problema, manje su bitne sintaksne greske, jer ti ne radis na racunaru nego pises. A logicno je da mozes da koristis sve metode iz API-a, ali u principu ti nece trebati neke posebne. Eventualno, pored gore vec pomenutih, jos i Math.abs() i tome slicno

Macro · **Poslato:** 30.08.2006. 18:08:56

Kod:

3. 

   (40)               (40)              (40)               (70) 
  /   \   +70 =      /    \    +55=     /   \     +150=    /  \ 
(20) (90)         (20)    (90)      (20)    (70)        (40)   (90) 
                         /                  /  \         / \      \ 
                       (70)               (55) (90)   (20) (55)   (150) 



            (70) 
+100=      /    \ 
       (40)      (100) 
       / \        /  \ 
   (20)  (55) (90)    (150) 


6. 
a) 
        (130)              (50)                    (50,130) 
        /  \     +25=      /  \         +100=      /   |   \ 
  (30,50)   (200)    (25,30)   (130,200)     (25,30) (100)  (200) 


            (50,130)                      (50 ,130) 
+180=      /   |    \        +120=       /    |    \ 
     (25,30) (100)  (180,200)     (25,30) (100,120) (180,200) 

  
                  (  130  ) 
                /          \ 
+150=    ( 50 )             ( 180 ) 
         /   \              /      \ 
   (25,30)   (100,120)  (150)       (200) 

b) 

        (130)             (50)                  
        /   \    -200=    /   \    -50= (30,130) -30= (130) 
  (30,50)   (200)     (30)    (130)         

Moze li neko da potvrdi da li je ovo dobro uradio/la nikornla

baneizalfe · **Poslato:** 31.08.2006. 02:29:59

Nesto sam gledao User-ovu skripte, extra je samo ima neke male greske. E sad mene neki zadaci malo i bune na primer:

Kod:

•   Dat je pokazivač na koren binartnog stabla čiji čvorovi sadrže cele brojeve. Napišite funkciju koja će vratiti broj čvorova koji su po sadržaju veći od svih svojih potomaka.
public static int potomci(TreeNode n1){
  int p1, p2;
  if(n == null)
    return 0;
  if(n.left.data > n.data) 
    p1 = 1;
  else
    p1 = 0;
  if(n.right.data > n.data)
    p2 = 1;
  else
    p2 = 0;
  return p1 + p2 + potomci(n.left) + potomci(n.right);
}

Kolko ja vidim, ovde se broje cvorovi koji su po sadrzaju manji od svih svojih potomaka. Zar ne bi trebalo:

Kod:

public static int potomci(TreeNode n1){
  int brojac; 
  if(n == null)
    return 0;
  if(n.data > n.left.data) && (n.data > n.right.data){
    brojac = 1;
  else
    brojac= 0;
  return brojac + potomci(n.left) + potomci(n.right);
}

Valjda nisam pogresio...

I ovo:

Kod:

Binarno stablo se naziva HEAP ako za svaki čvor u stablu važi da je njegov sadržaj veći od sadržaja svih ostalih čvorova u njegovim podstablima. Napisati funkciju koja će proveriti da li je dato binarno stablo celih brojeva HEAP.
public static boolean isHeap(TreeNode root){
        if (root == null)
          return true;
        if (root.left != null && (root.left.compareTo(root) > 0) || !isHeap(root.left)))
          return false;
        if (root.right != null && (root.right.compareTo(root) > 0 || !isHeap(root.right)))
          return false;
        return true;
      }
      // metod compareTo uporedjuje vrednost cvora sa artumentom, vraca 1 ako je veci
      // -1 ako je manji i 0 ako su jednaki

Lepo kaze ako je veci. Metoda lepo vraca -1, 0 i 1. Zar ne bi onda trebalo umesto > da bude >= , ha?

Macro · **Poslato:** 31.08.2006. 09:04:28

baneizalfe je napisao:

Kolko ja vidim, ovde se broje cvorovi koji su po sadrzaju manji od svih svojih potomaka. Zar ne bi trebalo:

Kod:

public static int potomci(TreeNode n1){
  int brojac; 
  if(n == null)
    return 0;
  if(n.data > n.left.data) && (n.data > n.right.data){
    brojac = 1;
  else
    brojac= 0;
  return brojac + potomci(n.left) + potomci(n.right);
}

Valjda nisam pogresio...

Da, da tvoj kod je OK.
Prvo sto ovaj kod iz User-ove, ne prebrojava samo sve vec i one kod kojih je levo ili desno podstablo manje.

FONForum

Strukture za sve

Ko je OnLine