h2. 'J-Arbore':problema/jarbore

Vom calcula $N[i]$, reprezentand cate noduri are arborele pe fiecare nivel (incepand de la $1$), precum si valoarea de pe prima muchie si de pe ultima muchie dintre nivelul $i-1$ si nivelul $i$ ({$v1[i] si v2[i]$}). Avem $N[1]=1$ si $v1[1]=v2[1]=0$. In cazul general, $N[i]=N[i-1]*(i-1)$, $v1[i]=v2[i-1]+1$ si $v2[i]=v1[i]+N[i]-1$. De asemenea, vom calcula cea mai mica si cea mai mare eticheta a unui nod de pe nivelul $i$: $vmin[i]=vmin[i-1]+v1[i]$ si $vmax[i]=vmax[i-1]+v2[i]$. Vom observa ca $24$ de nivele ale arborelui ajung pentru limitele date. Pentru fiecare numar $S$ dat vom gasi nivelul pe care s-ar afla (daca numarul exista in arbore), folosind valorile $vmin[i]$ si $vmax[i]$. Apoi, pentru a determina unde se afla numarul $S$, vom incerca sa deteminam pozitia acestuia in cadrul nivelului. Pentru aceasta vom realiza o cautare binara. Vom scrie o functie care va determina ce valoare se afla pe pozitia $p$ de pe nivelul $q$: aceasta valoare este valoare de pe pozitia $p/q$ de pe nivelul $q-1$, la care se adauga $v1[q]+p$ (considerand pozitiile numerotate de la $0$ in cadrul unui nivel). Vom determina astfel daca numarul $S$ exista si, daca da, vom reconstitui drumul de la el pana la radacina arborelui (ceea ce facem, oricum, in cadrul functiei de determinare a valorii de pe o pozitie $p$ de pe un nivel $q$).

Vom calcula $N[i]$, reprezentand cate noduri are arborele pe fiecare nivel (incepand de la $1$), precum si valoarea de pe prima muchie si de pe ultima muchie dintre nivelul $i-1$ si nivelul $i$ ({$v1[i] si v2[i]$}). Avem $N[ 1 ]=1$ si $v1[ 1 ]=v2[ 1 ]=0$. In cazul general, $N[i]=N[i-1]*(i-1)$, $v1[i]=v2[i-1]+1$ si $v2[i]=v1[i]+N[i]-1$. De asemenea, vom calcula cea mai mica si cea mai mare eticheta a unui nod de pe nivelul $i$: $vmin[i]=vmin[i-1]+v1[i]$ si $vmax[i]=vmax[i-1]+v2[i]$. Vom observa ca $24$ de nivele ale arborelui ajung pentru limitele date. Pentru fiecare numar $S$ dat vom gasi nivelul pe care s-ar afla (daca numarul exista in arbore), folosind valorile $vmin[i]$ si $vmax[i]$ (cautam acel nivel $i$ pentru care $vmin[i] ≤ S ≤ vmax[i]$) . Apoi, pentru a determina unde se afla numarul $S$, vom incerca sa deteminam pozitia acestuia in cadrul nivelului. Pentru aceasta vom realiza o cautare binara. Vom scrie o functie care va determina ce valoare se afla pe pozitia $p$ de pe nivelul $q$: aceasta valoare este valoare de pe pozitia $p/q$ de pe nivelul $q-1$, la care se adauga $v1[q]+p$ (considerand pozitiile numerotate de la $0$ in cadrul unui nivel). Vom determina astfel daca numarul $S$ exista si, daca da, vom reconstitui drumul de la el pana la radacina arborelui (ceea ce facem, oricum, in cadrul functiei de determinare a valorii de pe o pozitie $p$ de pe un nivel $q$).