Diferente pentru multe-smenuri-de-programare-in-cc-si-nu-numai intre reviziile #7 si #54

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Multe "smenuri" de programare in C/C++... si nu numai!
(Creat de '_domino_':user/domino la data de _2004-11-10_ categoria _Limbaje_, autor(i) _Mircea Pasoi_)
(Categoria _Limbaje de programare_, Autor _Mircea Pasoi_)
==Include(page="template/raw")==
 
Acest articol vine ca o completare a articolului scris de Alexandru Mosoi, prezentand noi trucuri care le-am folosit si m-au ajutat mult. O mare parte din acestea le-am invatat din sursele lui Radu Berinde (cred ca stiti cu totii cine este), asadar ii multumesc!
Acest articol vine ca o completare a articolului scris de Alexandru Mosoi, prezentand noi trucuri pe care le-am folosit si m-au ajutat mult. O mare parte din acestea le-am invatat din sursele lui Radu Berinde (cred ca stiti cu totii cine este), asadar ii multumesc!
h2. Array-uri neindexate de la 0
Un dezavantaj fata de Pascal este faptul ca in C nu putem avea expresii de genul {@A[-100]@} unde $A$ este un vector. Dar acest lucru se poate remedia. Spre exemplu, daca vrem sa facem un vector $A$ cu elemente de la $-100$ la $100$ procedam astfel:
{@int A[201];@}
{@#define A (A + 100)@}
== code(c) |
int A[201];
#define A (A + 100)
==
h2. Fisiere de intrare si iesire
Folositi {@freopen()@} in loc de {@fopen()@} deoarece este mai comod, in special la concursurile in care intrare si iesirea sunt standard.
{@freopen("in.txt", "r", stdin);@}
{@freopen("out.txt", "w", stdout);@}
== code(c) |
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
==
h2. Cautare binara (ideea originala de la Mihai Patrascu)
h2. Cautare binara
Urmatorul cod este de aproximativ $4$ ori mai rapid (am testat cu cautare binara ca in manual) , mai usor de inteles, mai flexibil si mai scurt... ce ati putea dori mai mult?
p(pre).
{@int N, A[N];@}
{@int binary_search(int val)@}
{@{@}
{@    int i, step;@}
{@    for (step = 1; step < N; step <<= 1);@}
{@    for (i = 0; step; step >>= 1)@}
{@        if (i + step < N && A[i + step] <= val)@}
{@           i += step;@}
{@    return i;@}
{@}@}
== code(c) |
int N, A[N];
 
int binary_search(int val)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && A[i + step] <= val)
           i += step;
    return i;
}
==
Procedura de mai sus face cautarea binara folosind puteri a lui $2$ in ordine descrescatoare, practic incerc sa determin fiecare bit al rezultatului.
h2. Impartire in bucati de marime $sqrt(n)$ (cunoscut si ca "smenul lui Bogdan Batog")
h2(#batog). Impartire in bucati de marime $sqrt(n)$ (cunoscut si ca "smenul lui Bogdan Batog")
Sa presupunem ca avem un vector de lungime n cu numere reale pe care se fac urmatoarele operatii:
{@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu $x$
{@SUMA(st, dr)@} - returneaza suma elementelor cu indicii intre $st$ si $dr$
Pentru cei ce cunosc arbori de intervale, rezolvarea acestei probleme in $O(lg n)$ per operatie este o munca usoara, dar presupunand ca nu stim aceasta structura putem folosi urmatorul truc: vom construi un al doilea vector de lungime $sqrt(n)$ care retine suma elementelor pe bucati de lungime {$sqrt(n)$}. Pentru a face o operatie pe un interval [{$st, dr$}] vom imparti acest interval in bucati de $sqrt(n)$ a caror actualizare o facem in vectorul $B$ si elementele care raman in margine in vectorul {$A$}. De exemplu pe vectorul {@A[0..15]@} vom avea vectorul {@B[0..3]@}. Pentru a actualiza de exemplu [{$2, 12$}] vom actualiza {@B[1]@} (care corespunde lui [{$4..7$}]), {@B[2]@} (pentru [{$8..11$}]) si {@A[2]@}, {@A[3]@}, {@A[12]@} (elementele din margini). Cum sunt maxim $sqrt(n)$ elemente de actualizat in $B$ si pe margini nu vom actualiza niciodata mai mult de $2 * sqrt(n)$ elemente putem concluziona ca operatiile vor avea complexitate {$O(sqrt(n))$}.
Pentru cei ce cunosc arbori de intervale, rezolvarea acestei probleme in $O(lg n)$ per operatie este o munca usoara, dar presupunand ca nu stim aceasta structura putem folosi urmatorul truc: vom construi un al doilea vector de lungime $sqrt(n)$ care retine suma elementelor pe bucati de lungime {$sqrt(n)$}. Pentru a face o operatie pe un interval [{$st, dr$}] vom imparti acest interval in bucati de $sqrt(n)$ a caror actualizare o facem in vectorul $B$ si elementele care raman in margine in vectorul {$A$}. De exemplu pe vectorul {$A{~0..15~}$} vom avea vectorul {$B{~0..3~}$}. Pentru a actualiza de exemplu [{$2, 12$}] vom actualiza {$B{~1~}$} (care corespunde lui [{$4..7$}]), {$B{~2~}$} (pentru [{$8..11$}]) si {$A{~2~}$}, {$A{~3~}$}, {$A{~12~}$} (elementele din margini). Cum sunt maxim $sqrt(n)$ elemente de actualizat in $B$ si pe margini nu vom actualiza niciodata mai mult de $2 * sqrt(n)$ elemente putem concluziona ca operatiile vor avea complexitate {$O(sqrt(n))$}.
Daca am avea aceeasi problema dar in doua dimensiuni, am putea face acelasi "smen" pentru fiecare linie pentru o complexitate $O(n*sqrt(n))$ per operatie, sau cu arbori de intervale pe fiecare linie {$O(n*lg n)$}. Putem, de asemenea obtine o complexitate $O(n)$ folosind urmatoarea impartire:
$A$ - pentru bucati $1 * 1$
$D$ - pentru bucati $sqrt(n) * 1$
Acest mod de reprezentare este o extindere directa a aceluiasi smen in doua dimensiuni. Aceasta idee poate fi folosita si pentru alte operatii: inmultire, minim, maxim, etc. In general, orice se poate rezolva cu acest "smen" se poate obtine la o complexitate mai buna cu arbori de intervale, dar merita sa stiti si aceasta ideea deoarece de multe ori scuteste din efortul de implementare, desi se pierde din viteza... alegerea voastra! ;)
h2. LCA in $O(sqrt(n))$ (ideea originala de la Radu Berinde)
h2. LCA in $O(sqrt(n))$
Daca nu stiti ce este LCA, va recomand sa cititi "articolul":http://www.infoarena.ro/LCA_Lowest_common_ancestor lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in $sqrt(H)$ intervale in functie de inaltime, unde $H$ e inaltimea maxima (de exemplu la $H=9$ nodurile cu inaltimi intre $0$ si $2$ vor forma un interval, [{$3..5$}] alt interval si ultimul interval de inaltimi [{$6..8$}]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurede DF. In continuare, codul:
Daca nu stiti ce este LCA, va recomand sa cititi 'articolul':lowest-common-ancestor lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in $sqrt(H)$ intervale in functie de inaltime, unde $H$ e inaltimea maxima (de exemplu la $H=9$ nodurile cu inaltimi intre $0$ si $2$ vor forma un interval, [{$3..5$}] alt interval si ultimul interval de inaltimi [{$6..8$}]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurgere DF. In continuare, codul:
$H$ se calculeaza inainte sau poate fi constant
$T$ sunt tatii nodului si $N$ numarul de noduri
p(pre).
{@void DF(int n, int t2, int lev)@}
{@{@}
{@    int i;@}
{@    T2[n] = t2, Lev[n] = lev;@}
{@    if (lev % H == 0) t2 = n;@}
{@    for (i = 0; i < N; i++)@}
{@        if (T[i] == n) DF(i, t2, lev+1);@}
{@}@}
== code(c) |
void DF(int n, int t2, int lev)
{
    int i;
    T2[n] = t2, Lev[n] = lev;
    if (lev % H == 0) t2 = n;
    for (i = 0; i < N; i++)
        if (T[i] == n) DF(i, t2, lev+1);
}
==
Operatia de LCA se va realiza apoi foarte usor, urcand pe tatii din intervale, pana se ajunge la doua noduri in acelasi interval, apoi folosindu-se metoda clasica. Cod:
== code(c) |
int LCA(int x, int y)
 
{
while (T2[x] != T2[y])
if (Lev[x] > Lev[y])
x = T2[x];
else
y = T2[y];
 
while (x != y)
if (Lev[x] > Lev[y])
x = T[x];
else
y = T[y];
return x;
    while (T2[x] != T2[y])
        if (Lev[x] > Lev[y])
            x = T2[x];
        else
            y = T2[y];
    while (x != y)
        if (Lev[x] > Lev[y])
            x = T[x];
        else
            y = T[y];
    return x;
}
==
h2. LCA in $O(lg^2^ n)$
h2. LCA in O(lg^2 n)
 
Aceeasi problema, dar o alta rezolvare. Vom construi o matrice A[i][j] cu semnificatia A[i][j] = al 2^i-lea tata al nodului j. Folosind aceasta matrice putem cauta binar (O(lg n)) nivelul pe care s-ar putea afla LCA-ul a doua noduri si sa determinam daca nodul ales este corect - adica daca nodul situat la acel nivel este acelasi pentru cele doua noduri pentru care se face LCA (O(lg n) cu matricea de mai sus). Complexitate finala O(lg^2 n) si O(n*lg n) memorie.
Aceeasi problema, dar o alta rezolvare. Vom construi o matrice $A{~i,j~}$ cu semnificatia $A{~i,j~}$ = al {$2^i^$}-lea tata al nodului {$j$}. Folosind aceasta matrice putem cauta binar ({$O(lg n)$}) nivelul pe care s-ar putea afla LCA-ul a doua noduri si sa determinam daca nodul ales este corect - adica daca nodul situat la acel nivel este acelasi pentru cele doua noduri pentru care se face LCA ({$O(lg n)$} cu matricea de mai sus). Complexitate finala $O(lg^2^ n)$ si $O(n*lg n)$ memorie.
h2. For-uri "complicate"
for-ul in C/C++ este foarte flexibil si poate ajuta foarte mult in compactarea codului, deci si a timpului de implementare. In continuare vom prezenta algoritmul merge sort (sortare prin interclasare) scris in cateva linii (putine, zic eu!):
== code(c) |
int N, A[N], B[N];
 
void merge_sort(int l, int r)
{
int m = (l + r) >> 1, i, j, k;
 
if (l == r) return;
 
merge_sort(l, m);
merge_sort(m + 1, r);
 
 
 
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && A[i] < A[j]))
B[k++] = A[i++];
else
B[k++] = A[j++];
for (k = l; k <= r; k++) A[k] = B[k];
    int m = (l + r) >> 1, i, j, k;
    if (l == r) return;
    merge_sort(l, m);
    merge_sort(m + 1, r);
    for (i=l, j=m+1, k=l; i<=m || j<=r; )
        if (j > r || (i <= m && A[i] < A[j]))
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    for (k = l; k <= r; k++) A[k] = B[k];
}
==
h2. Recomandari generale
I. Programare dinamica cu memoizare: mult mai simplu si uneori chiar mai rapida cand nu ne trebuie tot array-ul
 
II. Algoritmi randomizati: de multe ori mai usor de implementat si mai eficienti, mai bine decat cei euristici, dar necesita o analiza mult mai atenta a performantei. Exemple calsice: quciksort, statistici de ordine
 
 
# Programare dinamica cu memoizare: mult mai simplu si uneori chiar mai rapida cand nu ne trebuie tot array-ul
# Algoritmi randomizati: de multe ori mai usor de implementat si mai eficienti, mai bine decat cei euristici, dar necesita o analiza mult mai atenta a performantei. Exemple clasice: quicksort, statistici de ordine
h2. "Smenul lui Mars" (Marius Andrei)
Consideram urmatoarea problema: se da un vector A de N elemente pe care se fac M astfel de operatii: ADUNA(st, dr, x) - toate elementele cu indicii intre st si dr isi cresc valoarea cu x. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de O(1) pentru operatia ADUNA si O(N) pentru a determina un element din vector. Vom construi un al doilea vector B de N+1 elemente, cu proprietatea ca A[i] = B[0] + B[1] + ... B[i]. Astfel, o operatie ADUNA(st, dr, x) devine:
Consideram urmatoarea problema: se da un vector $A$ de $N$ elemente pe care se fac $M$ astfel de operatii: {@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ ({$0 &le; st &le; dr &lt; N$}) isi cresc valoarea cu {$x$} . La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de $O(1)$ pentru operatia $ADUNA$ si $O(N)$ pentru a determina toate elementele din vector. Vom construi un al doilea vector $B$ de $N+1$ elemente, cu proprietatea ca {$A{~i~} = B{~0~} + B{~1~} + ... B{~i~}$}. Astfel, o operatie {@ADUNA(st, dr, x)@} devine:
B[st] += x;
== code(c) |B[st] += x;
B[dr + 1] -= x;
==
Da, este chiar asa de simplu! Pentru a determina un element A[i] vom aduna pur si simplu B[0] + B[1] + ... B[i]. Incercati pe foaie sa vedeti cum funtioneaza. Aceasta ideea poate fi extinsa si in doua dimensiuni, construind B astfel incat A[i][j] = suma subtabloului din B cu coltul in (0, 0) si (i, j), astfel (pt. ADUNA(x1,y1,x2,y2,v)):
Da, este chiar asa de simplu! Pentru a determina un element A{~i~} vom aduna pur si simplu {$B{~0~} + B{~1~} + ... B{~i~}$}. Incercati pe foaie sa vedeti cum funtioneaza. Aceasta ideea poate fi extinsa si in doua dimensiuni, construind $B$ astfel incat $A{~i,j~}$ = suma subtabloului din $B$ cu coltul in ({$0, 0$}) si ({$i, j$}), astfel (pt. {@ADUNA(x1,y1,x2,y2,v)@}):
B[x1][y1] += v;
== code(c) |B[x1][y1] += v;
B[x1][y2 + 1] -= v;
B[x2 + 1][y1] -= v;
B[x2 + 1][y2 + 1] += v;
==
Pe cazul general, daca vrem sa facem operatii in d dimensiuni vom avea o complexitate O(2^d). Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor, deoarece aflarea unui element este o operatie foarte ineficienta.
Pe cazul general, daca vrem sa facem operatii in $d$ dimensiuni vom avea o complexitate {$O(2^d^)$}. Reamintesc ca aceasta metoda este eficienta doar cand se vrea afisata vectorul/matricea/etc. doar la sfarsitul operatiilor sau sunt foarte putine interogari ale valorilor elementelor, deoarece aflarea unui element este o operatie foarte ineficienta: {$O(i)$} pentru a afla valorile elementelor pana la pozitia $i$.
h2. Grafuri cu liste de adiacenta (ideea originala de la Radu Berinde)
h2. Grafuri cu liste de adiacenta
Se stie (sau ar trebui sa se stie!) ca lucrul cu pointerii este foarte incet... astfel, cand retinem un graf rar (numar mare de noduri, numar mic de muchii) cu pointeri (vezi mai jos) incetinim foarte mult programul.
== code(c) |
struct list
{
int n;
struct list *next;
    int n;
    struct list *next;
}
typedef struct list list;
==
In contiuare vom prezenta o metoda care este de 3-4 ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de 3-4 ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.
In contiuare vom prezenta o metoda care este de $3-4$ ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de $3-4$ ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.
== code(c) |
#include <stdlib.h>
 
#include <stdio.h>
 
 
int N, M, *G[N], Deg[N];
 
 
int main(void)
{
    int i, j;
 
    freopen("in.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    for (; M > 0; M--)
    {
        scanf("%d %d", &i, &j);
        Deg[i - 1]++, Deg[j - 1]++;
    }
    for (i = 0; i < N; Deg[i++] = 0)
        G[i] = (int *) malloc(Deg[i]*sizeof(int));
    fseek(stdin, 0, SEEK_SET);
    scanf("%d %d", &N, &M);
    for (; M > 0; M--)
    {
        scanf("%d %d", &i, &j);
        i--, j--;
        G[i][Deg[i]++] = j,
            G[j][Deg[j]++] = i;
    }
int i, j;
 
 
 
freopen("in.txt", "r", stdin);
 
scanf("%d %d", &N, &M);
 
for (; M > 0; M--)
 
{
 
scanf("%d %d", &i, &j);
 
Deg[i - 1]++, Deg[j - 1]++;
 
}
 
 
 
for (i = 0; i < N; Deg[i++] = 0)
G[i] = (int *) malloc(Deg[i]*sizeof(int));
 
fseek(stdin, 0, SEEK_SET);
 
scanf("%d %d", &N, &M);
 
for (; M > 0; M--)
 
{
 
scanf("%d %d", &i, &j);
 
i--, j--;
 
G[i][Deg[i]++] = j,
 
G[j][Deg[j]++] = i;
 
}
 
    return 0;
}
==
Sporul de viteza se datoreaza faptului ca se folosesc vectori in loc de pointeri si struct-uri. Daca ne permite memoria putem evita citirea de doua ori a fisierul prin pastrarea muchiilor intr-o lista de muchii si apoi, dupa calcularea gradelor, inserarea muchiilor in liste. Pentru a demonstra eficienta acestei metode faceti urmatorul test: implementati o sursa cu pointeri si struct si implementati un BF, apoi scrieti codul de mai sus cu urmatoarele modificari:
== code(c) |
...
 
for (i = 0; i < N; i++)
 
{
 
G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));
 
G[i][Deg[i]] = -1;
 
Deg[i] = 0;
 
      G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));
      G[i][Deg[i]] = -1;
      Deg[i] = 0;
}
 
...
==
si implementati BF astfel:
void BF(int n)
 
== code(c) |
void BF()
{
 
int Q[N], ql, qr, *p;
 
char U[N];
 
 
 
memset(U, 0, sizeof(U));
 
U[Q[ql = qr = 0] = n] = 1;
 
for (; ql <= qr; ql++)
 
for (p = G[Q[ql]]; *p != -1; p++)
 
if (!U[*p]) U[Q[++qr] = *p] = 1;
      int Q[N], ql, qr, *p;
      char U[N];
      memset(U, 0, sizeof(U));
      U[Q[ql = qr = 0] = n] = 1;
      for (; ql <= qr; ql++)
              for (p = G[Q[ql]]; *p != -1; p++)
                      if (!U[*p]) U[Q[++qr] = *p] = 1;
}
==
Apoi, incercati sa vedeti diferenta de timp intre cele doua programe... impresionant, nu?
h2. Numere mari (ideea originala de la Radu Berinde)
h2. Numere mari
In continuare voi prezenta cum se pot realiza operatii pe numere mari cu foarte putine linii de cod. In general, multi programatori se complica la aceste operatii, desi nu este nevoie! Vom considera ca numerele mari sunt vectori in care elementul de indice 0 indica lungimea numarului, iar cifrele sunt retinute in ordinea inversa decat cea a citirii.
In continuare voi prezenta cum se pot realiza operatii pe numere mari cu foarte putine linii de cod. In general, multi programatori se complica la aceste operatii, desi nu este nevoie! Vom considera ca numerele mari sunt vectori in care elementul de indice $0$ indica lungimea numarului, iar cifrele sunt retinute in ordinea inversa decat cea a citirii.
h3. Suma a doua numere mari
== code(c) |
void add(int A[], int B[])
{
int i, t = 0;
 
 
 
for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
A[i] = (t += A[i] + B[i]) % 10;
A[0] = i - 1;
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % 10;
      A[0] = i - 1;
}
==
h3. Inmultirea unui numar mare cu un numar mic
== code(c) |
void mul(int A[], int B)
{
int i, t = 0;
 
 
 
for (i = 1; i <= A[0] || t; i++, t /= 10)
A[i] = (t += A[i] * B) % 10;
A[0] = i - 1;
      int i, t = 0;
      for (i = 1; i <= A[0] || t; i++, t /= 10)
              A[i] = (t += A[i] * B) % 10;
      A[0] = i - 1;
}
==
h3. Inmultirea unui numar mare cu un numar mare
== code(c) |
void mul(int A[], int B[])
{
int i, j, t, C[];
 
 
 
memset(C, 0, sizeof(C));
for (i = 1; i <= A[0]; i++)
{
for (t=0, j=1; j <= B[0] || t; j++, t/=10)
C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
if (i + j - 2 > C[0]) C[0] = i + j - 2;
}
memcpy(A, C, sizeof(C));
      int i, j, t, C[NR_CIFRE];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}
==
h3. Scaderea a doua numere mari
== code(c) |
void sub(int A[], int B[])
{
int i, t = 0;
 
 
 
for (i = 1; i <= A[0]; i++)
A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;
for (; A[0] > 1 && !A[A[0]]; A[0]--);
      int i, t = 0;
      for (i = 1; i <= A[0]; i++) {
              A[i] -= ((i <= B[0]) ? B[i] : 0) + t;
              A[i] += (t = A[i] < 0) * 10;
      }
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
==
h3. Impartirea unui numar mare la un numar mic
== code(c) |
void div(int A[], int B)
{
int i, t = 0;
 
 
 
for (i = A[0]; i > 0; i--, t %= B)
A[i] = (t = t * 10 + A[i]) / B;
for (; A[0] > 1 && !A[A[0]]; A[0]--);
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
==
h3. Restul unui numar mare la un numar mic
== code(c) |
int mod(int A[], int B)
{
int i, t = 0;
 
 
 
for (i = A[0]; i > 0; i--)
t = (t * 10 + A[i]) % B;
return t;
      int i, t = 0;
      for (i = A[0]; i > 0; i--)
              t = (t * 10 + A[i]) % B;
      return t;
}
==
h2(#AVL). AVL-uri (implementarea lui Radu Berinde)
AVL-urile sunt arbori de cautare echilibrati care au complexitate O(lg n) pe operatiile de inserare, stergere si cautare. Pentru mai multe detalii cautati cartea "Arbori" pe site-ul doamnei profesoare Emanuela Cerchez. In continuare voi prezenta o metoda destul de simpla de a implementa aceastra structura de date in timp de concurs. Enjoy!
h2. AVL-uri (ideea originala de la Radu Berinde - again)
 
AVL-urile sunt arbori de cautare echilibrati care au complexitate O(lg n) pe operatiile de inserare, stergere si cautare. Pentru mai multe detalii cautati cartea "Arbori" pe [2]site-ul doamnei profesoare Emanuela Cerchez. In continuare voi prezenta o metoda destul de simpla de a implementa aceastra structura de date in timp de concurs. Enjoy!
 
== code(c) |
#define max(a, b) ((a) > (b) ? (a) : (b))
#define geth(n) (n->h = 1 + max(n->l->h, n->r->h))
 
 
struct node
{
int key, h;
struct node *l, *r;
      int key, h;
      struct node *l, *r;
} *R, *NIL;
typedef struct node node;
 
 
void init(void)
{
R = NIL = (node *) malloc(sizeof(node));
NIL->key = NIL->h = 0,
 
NIL->l = NIL->r = NULL;
      R = NIL = (node *) malloc(sizeof(node));
      NIL->key = NIL->h = 0,
              NIL->l = NIL->r = NULL;
}
 
 
node* rotleft(node *n)
{
node *t = n->l;
      node *t = n->l;
n->l = t->r, t->r = n,
geth(n), geth(t);
return t;
      n->l = t->r, t->r = n,
              geth(n), geth(t);
      return t;
}
 
 
node* rotright(node *n)
{
node *t = n->r;
 
n->r = t->l, t->l = n,
geth(n), geth(t);
return t;
      node *t = n->r;
 
      n->r = t->l, t->l = n,
              geth(n), geth(t);
      return t;
}
 
 
node* balance(node *n)
{
geth(n);
if (n->l->h > n->r->h + 1)
{
if (n->l->r->h > n->l->l->h)
n->l = rotright(n->l);
n = rotleft(n);
}
else
if (n->r->h > n->l->h + 1)
{
if (n->r->l->h > n->r->r->h)
n->r = rotleft(n->r);
n = rotright(n);
      geth(n);
      if (n->l->h > n->r->h + 1)
      {
              if (n->l->r->h > n->l->l->h)
                      n->l = rotright(n->l);
              n = rotleft(n);
      }
      else
              if (n->r->h > n->l->h + 1)
              {
                      if (n->r->l->h > n->r->r->h)
                              n->r = rotleft(n->r);
                      n = rotright(n);
              }
      return n;
}
return n;
}
 
 
node* insert(node *n, int key)
{
if (n == NIL)
{
n = (node *) malloc(sizeof(node));
n->key = key, n->h = 1, n->l = n->r = NIL;
return n;
}
if (key < n->key)
n->l = insert(n->l, key);
else
n->r = insert(n->r, key);
return balance(n);
      if (n == NIL)
      {
              n = (node *) malloc(sizeof(node));
              n->key = key, n->h = 1, n->l = n->r = NIL;
              return n;
      }
      if (key < n->key)
              n->l = insert(n->l, key);
      else
              n->r = insert(n->r, key);
      return balance(n);
}
 
 
node* erase(node *n, int key)
{
node *t;
 
if (n == NIL) return n;
if (n->key == key)
{
if (n->l == NIL || n->r == NIL)
{
t = n->l == NIL ? n->r : n->l;
free(n); return t;
      node *t;
      if (n == NIL) return n;
      if (n->key == key)
      {
              if (n->l == NIL || n->r == NIL)
              {
                      t = n->l == NIL ? n->r : n->l;
                      free(n); return t;
              }
              else
              {
                      for (t = n->r; t->l != NIL; t = t->l);
                      n->key = t->key,
                              n->r = erase(n->r, t->key);
                      return balance(n);
              }
      }
      if (key < n->key)
              n->l = erase(n->l, key);
      else
              n->r = erase(n->r, key);
      return balance(n);
}
else
{
for (t = n->r; t->l != NIL; t = t->l);
n->key = t->key,
 
n->r = erase(n->r, t->key);
return balance(n);
}
}
if (key < n->key)
n->l = erase(n->l, key);
else
n->r = erase(n->r, key);
return balance(n);
}
 
 
int search(node *n, int key)
{
if (n == NIL) return 0;
if (n->key == key) return 1;
if (key < n->key)
return search(n->l, key);
else
return search(n->r, key);
      if (n == NIL) return 0;
      if (n->key == key) return 1;
      if (key < n->key)
              return search(n->l, key);
      else
              return search(n->r, key);
}
==
Aici se termina acest articol. Am incercat sa pun accentul pe simplitate si eficienta, si cred ca am reusit acest lucru. Sper ca ati invatat cate ceva din el si recomand sa luati fiecare bucata in parte si sa incercati sa implementati efectiv ca sa intelegi mai bine. Bafta la concursuri tuturor! ;)
 
References
 
Visible links
1. http://info.devnet.ro/articole.php?page=art&art=19
2. http://www.liis.ro/%7eema/
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3673