infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Popescu Silviu din Septembrie 01, 2011, 17:29:49

Titlul: Memorie Arbore de Intervale
Scris de: Popescu Silviu din Septembrie 01, 2011, 17:29:49

Salut , cata memorie iti trebuie pentru un Arbore de Intervale.
Mie mi-a dat ca trebuie sa aiba 2*N-1 noduri daca are N frunze, dar cred ca e gresit.

Multumesc pt ajutor :D

Titlul: RÄƒspuns: Memorie Arbore de Intervale
Scris de: cont cu nume gresit sau fals din Septembrie 01, 2011, 17:31:36

trebuie sa aiba 2*x-1 (unde x e cea mai mica putere a lui 2 mai mare sau egala cu n)

Titlul: RÄƒspuns: Memorie Arbore de Intervale
Scris de: Popescu Silviu din Septembrie 01, 2011, 17:45:08

Nu merge, adica uite-te pt cazul N=3 ai:

Cod:

         [1,3]
        /     \
    [1,2]    [3]
    /    \
  [1]   [2]

2*4-1 != 5

Ms oricum, m-am prins, e bine 2*N-1
Intrebam pt ca daca puneam memoria 2*N-1 la probleme imi dade KBS11, acum mi-am dat seama k tre sa pui memoria
2^[lgN]+1 ca sa nu se intample :oops:

Titlul: RÄƒspuns: Memorie Arbore de Intervale
Scris de: cont cu nume gresit sau fals din Septembrie 01, 2011, 17:56:05

nu inteleg ce vrei sa zici.
eu pt 3 tin arborele de intervale asa:

Cod:

          [1,4]
        /        \
    [1,2]       [3,4]
    /    \         /  \
  [1]   [2]   [3]    [4]

          1
         /  \
       2     3
      / \    / \ 
    4   5   6   7

deasemenea vezi ca 2*x-1 (unde x e cea mai mica putere a lui 2 mai mare sau egala cu n) inseamna 2^[log₂n]+1-1,
unde [ x ], inseamna parte intreaga superioara a lui x