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

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Multe "smenuri" de programare in C/C++... si nu numai!
(Categoria _Limbaje_, autor(i) _Mircea Pasoi_)
(Categoria _Limbaje de programare_, Autor _Mircea Pasoi_)
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
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?
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$
$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':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 parcurgere 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
h2. Recomandari generale
# 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 calsice: quicksort, statistici de ordine
# 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)
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.
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.
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 (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]--);
}
==
}
==
h2(#AVL). AVL-uri (ideea originala de la Radu Berinde - again)
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 [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!
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!
== code(c) |
#define max(a, b) ((a) > (b) ? (a) : (b))

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3673