Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.
Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.
Algoritmul lui Kruskal permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.
Pentru a determina APM-ul se pleacă de la o pădure formată din N subarbori. Fiecare nod al grafului reprezintă inițial un subarbore. Aceștia vor fi reuniți succesiv prin muchii, până când se obține un singur arbore (dacă graful este conex) sau până când acest lucru nu mai este posibil (dacă graful nu este conex).
Algoritmul este:
Principala dificultate în algoritmul descris mai sus este stabilirea faptului că extremitățile muchiei curente fac sau nu parte din același subarbore. În acest scop vom stabili pentru fiecare subarbore un nod special, numit reprezentant al (sub)arborelui și pentru fiecare nod din graf vom memora reprezentantul său (de fapt al subarborelui din care face parte) într-un tablou unidimensional.
Pentru a stabili dacă două noduri fac sau nu parte din același subarbore vom verifica dacă ele au același reprezentant. Pentru a reuni doi subarbori vom înlocui pentru toate nodurile din subarborele B cu reprezentantul subarborelui A.
Înlocuirile descrise mai sus sunt simple dar lente. Pentru o implementare mai eficientă a algoritmului se poate folosi conceptul de Padure de mulțimi disjuncte, descris în acest articol.
Vom determina, folosind Algoritmul lui Kruskal, arborele parțial de cost minim pentru graful de mai jos.

Muchiile se vor analiza în ordinea crescătoare a costului.

Se adaugă muchia (7,8) de cost 1

Se adaugă muchia (3,9) de cost 2

Se adaugă muchia (6,7) de cost 2

Se adaugă muchia (1,2) de cost 4

Se adaugă muchia (3,6) de cost 1
Se ignoră muchia (7,9) de cost 6

Se adaugă muchia (3,4) de cost 7

Se ignoră muchia (8,9) de cost 7

Se adaugă muchia (1,8) de cost 8

Se ignoră muchia (2,3) de cost 8

Se adaugă muchia (4,5) de cost 9

Se ignoră muchia (5,6) de cost 10

Se ignoră muchia (2,8) de cost 11

Se ignoră muchia (4,6) de cost 14
Vom determina, folosind Algoritmul lui Kruskal, arborele parțial de cost minim pentru graful de mai jos:

Muchiile se vor analiza în ordinea următoare:
| 1. | |
Se adaugă muchia (7,8) de cost 1 |
| 2. | |
Se adaugă muchia (3,9) de cost 2 |
| 3. | |
Se adaugă muchia (6,7) de cost 2 |
| 4. | |
Se adaugă muchia (1,2) de cost 4 |
| 5. | |
Se adaugă muchia (3,6) de cost 1 |
| 6. | |
Se ignoră muchia (7,9) de cost 6 |
| 7. | |
Se adaugă muchia (3,4) de cost 7 |
| 8. | |
Se ignoră muchia (8,9) de cost 7 |
| 9. | |
Se adaugă muchia (1,8) de cost 8 |
| 10. | |
Se ignoră muchia (2,3) de cost 8 |
| 11. | |
Se adaugă muchia (4,5) de cost 9 |
| 12. | |
Se ignoră muchia (5,6) de cost 10 |
| 13. | |
Se ignoră muchia (2,8) de cost 11 |
| 14. | |
Se ignoră muchia (4,6) de cost 14 |
Următoarea secvență determină costul total al APM-ului, folosind algoritmul lui Kruskal. Presupunem că graful are cel mult 100 de noduri.
struct muchie{
int i,j,cost;
};
int n , m , t[101];
muchie x[5000];
int main()
{
cin >> n >> m;
for(int i = 0 ; i < m ; ++i)
cin >> x[i].i >> x[i].j >> x[i].cost;
//sortare tablou x[] după campul cost
// ... de completat
//initializare reprezentanti
for(int i =1 ; i <= n ; ++i)
t[i] = i;
//determinare APM
int S = 0;
for(int i = 0 ; i < m ; i ++)
if(t[x[i].i] != t[x[i].j]) // extremitatile fac parte din subrabori diferiti
{
S += x[i].cost;
//reunim subarborii
int ai = t[x[i].i], aj = t[x[i].j];
for(int j =1 ; j <= n ; ++j)
if(t[j] == aj)
t[j] = ai;
}
cout << S << "\n";
return 0;
}
Operațiile standard de intrare/ieșire se fac cu tastatură și ecranul, dar este posibil să realizăm și citiri din fișiere text, respectiv scrieri în fișiere text. Pentru a realiza operațiile propriu-zise, fișierele sunt asociate cu fluxuri de date, iar operațiile sunt similare cu cele cu tastatura și ecranul.
În C++ există mai multe modalități de lucru cu fișiere text. Toate respectă următoarele etape:
O modalitate uzuală de a deschide fișiere constă în declararea unor variabile de tip flux. Acestea sunt de tip:
ofstream pentru fluxurile de ieșire – asociate cu fișierele în care vom scrie;ifstream pentru fluxurile de intrare – asociate cu fișierele din care vom citi;Declararea variabilelor se poate face astfel:
ifstream fin(NUME_FISIER_INTRARE); ofstream fout(NUME_FISIER_IESIRE);
NUME_FISIER_INTRARE și NUME_FISIER_IESIRE sunt șiruri de caractere care conțin numele fișierelor din care se face citirea/în care se face scrierea, de exemplu:
ifstream fin("fisier.in");
ofstream fout("fisier.out");
Nu este obligatoriu să folosim extensiile .in și .out, dar ele sunt frecvent folosite în algoritmică, pentru a desemna fișierul de intrare (INput), respectiv fișierul de ieșire (OUTput.)
fin și fout sunt identificatori de variabile. Putem folosi orice identificator, dar alegerea unor nume clare precum fin și fout, sau is (input stream) și os (output stream) fac, considerăm noi, programele mai ușor de înțeles și depanat.
Secvența de mai sus realizează simultan două operații: declararea variabilei de tip flux și dechiderea acestuia (asocierea cu fișierul corespunzător). Ele pot fi realizate și independent, de exemplu astfel:
ifstream fin;
fin.open("fisier.in");
sau
fstream fin("fisier.in", ios::in), fout("fisier.out", ios::out);
Declararea variabilelor de tip flux se poate face oriunde, cu respectarea restricțiilor cunoscute: orice variabilă folosită trebuie să fi fost anterior declarată.
Pentru citirea propiu-zisă a datelor din fișier/scrierea datelor în fișier se folosesc operatorii de extracție din flux/inserare în flux.
De exemplu:
int x; fin >> x; fout << 2 * x;
Se face astfel:
fin.close(); fout.close();
Următorul program este soluție corectă pentru problema #sum :
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sum.in");
ofstream fout("sum.out");
int main()
{
int a , b, s;
fin >> a >> b;
fin.close();
s = a + b;
fout << s;
fout.close();
return 0;
}
fin >> ...) vor eșua și comportamentul programului devine de multe ori impredictibil;Ridicarea la putere este o operație binecunoscută, formulă uzuală fiind: $$ A^n = \prod_{i=1}^n {A} = \underbrace{A \times A \times … \times A }_{\text{de } n \text{ ori}} $$
Un algoritm care implementează această metodă va avea complexitate liniară, \(O(n)\):
int Putere(int A , int n)
{
int P = 1 ;
for(int i = 1 ; i <= n ; i ++)
P = P * A;
return P;
}
O metodă mai bună este cea numită exponențierea rapidă , sau ridicarea la putere în timp logaritmic, complexitatea sa fiind \(O(\log_2{n})\). Ea se bazează pe următoarea formulă:
$$ A^n = \begin{cases} 1& \text{, dacă } n = 0\\ A \cdot A^{n-1}& \text{, dacă } n \text{ – impar}\\ {\left(A^{\frac{n}{2}}\right)}^2& \text{, dacă } n \text{ – par} \end{cases}$$
Să calculăm \(2^{25}\):
25 este impar24 este par12 este par6 este par3 este impar2 este par1 este imparAtunci în ordine inversă:
Constatăm că numărul înmulțirilor efectuate este mult mai mic decât în cazul primei metode.
Implementarea recursivă este directă:
int Putere(int A , int n)
{
if(n == 0)
return 1;
if(n % 2 == 1)
return A * Putere(A , n - 1);
int P = Putere(A , n / 2);
return P * P;
}
Să considerăm \(A^{25}\). Să-l scriem pe \(25\) ca sumă de puteri ale lui \(2\) (orice număr natural poate fi scris ca sumă de puteri ale lui \(2\) într-un singur mod): \(25 = 1 + 8 + 16\).
Atunci \( A^{25} = A^{1 + 8 + 16} = A^1 \cdot A^8 \cdot A^{16} = \underbrace{{(A^1)}^1}_{=A^1} \cdot \underbrace{{(A^2)}^0}_{=1} \cdot \underbrace{{(A^4)}^0}_{=1} \cdot \underbrace{{(A^8)}^1}_{=A^8} \cdot \underbrace{{(A^{16})}^1}_{=A^{16}}\). Observăm că exponenții \(0\) și \(1\) sunt cifrele reprezentării în baza \(2\) a lui \(25\).
Se figurează următoarea idee, pentru a determina An:
P, format din factori de forma A1, A2, A4, A8, …2 a lui n, începând cu cea mai nesemnificativă:
1, înmulțim pe A la P, P = P * A;A cu el însuși, A = A * A;, obținând următoarea putere din șirul de mai susImplementare C++:
int Putere(int A , int n)
{
int P = 1;
while(n)
{
if(n % 2 == 1)
P = P * A;
A = A * A;
n /= 2;
}
return P;
}
altă variantă, care folosește operațiile pe biți:
int Putere(int A , int n)
{
int P = 1;
for(int k = 1 ; k <= n ; k <<= 1)
{
if((n & k))
P *= A;
A = A * A;
}
return P;
}
În numeroase probleme de informatică se cere determinarea restului împărțirii unui anumit număr (de regulă rezultat ale unui calcul) la o valoare dată, N. De cele mai multe ori numărul nu poate fi determinat direct, valoarea sa fiind prea mare. În aceste situații intervine aritmetica modulară, în care restul cerut se determină facând operații cu resturi la împărțirea cu N a unor rezultate parțiale.
Fie \( N > 1\) un număr natural și două numere întregi \(a\) și \(b\). Spunem că \(a\) și \(b\) sunt congruente modulo \(N\) , \( a \equiv b \mod N \) dacă \( N \vert (a-b) \). Echivalent, dacă \(a\) și \(b\) dau același rest la împărțirea cu \(N\).
Avem următoarele reguli – spunem că congruența modulo N este compatibilă cu adunarea și înmulțirea numerelor întregi :
Consecințe (C/C++):
a, b, iar N > 1 unu număr natural:
N este (a + b) % N = (a % N + b % N) % NN este (a * b) % N = ((a % N) * (b % N)) % Nn numere naturale A[1], A[2], …, A[n], restul împărțirii la N a produsului lor se determină astfel:int P = 1;
for(int i =1 ; i <= n ; i ++)
P = (P * A[i]) % N;
N a lui N! – N factorial:int P = 1;
for(int i =1 ; i <= N ; i ++)
P = (P * i) % N;
Fie numerele naturale a ≥ b și N>1. Deși congruența modulo N este compatibilă cu operația de scădere, expresia (a-b)%N = (a%N-b%N)%N nu este întotdeauna corectă.
Mai precis, chiar dacă a > b, deci (a-b)%N≥0, expresia (a%N-b%N) și deci (a%N-b%N)%N poate fi negativă. Situatia poate fi rezolvată ușor, adunând la X=(a%N-b%N)%N valoarea N, astfel X nemaifiind negativ.
Exemplu: Fie n m, două numere naturale, 1 ≤ n ≤ m ≤ 1000. Determinați restul împărțirii lui m!-n! la 1009.
Rezolvare: Fie N = 1009. Deoarece numere sunt mari, nu putem calcula factorialele. Vom calcula A = m! % N, B= n! % N, apoi X = (A-B)%N. Dacă X este negativ, vom aduna la X valoarea N, acesta fiind și rezultatul.
Următoarea secvență C++ implementează ideea de mai sus:
int n , m;
const int N = 1009;
cin >> n >> m; // n <= m
int A = 1, B = 1;
for(int i = 1 ; i <= m ; i ++)
A = (A * i) % N;
for(int i = 1 ; i <= n ; i ++)
B = (B * i) % N;
int X = A - B;
if(X < 0)
X += N;
cout << X;
Congruența modulo N nu este compatibilă cu împărțirea. Consecința este că (B/A) % N != ((B % N)/(A % N)) % N. Pentru a determina rezultatul modulo N al unor expresii în care intervin împărțiri vom folosi inversul modular.
Acesta permite transformarea expresiei B/A % N într-o înmulțire și poate fi determinat numai dacă numerele A și N sunt prime între ele.
Mai precis, dacă 1 ≤ A < N, inversul lui A modulo N este un număr natural 1 ≤ A-1 < N cu proprietatea că \( A \cdot A^{-1} \equiv 1 \mod N \). Atunci (B/A) % N = (B * A-1) % N = ((B%N)*(A-1%N))%N.
Există mai multe modalități de a determina inversul modular. În cele ce urmează vom nota inversul modular al lui A cu I.
O primă variantă este să analizăm fiecare număr k cuprins între 1 și N-1. Dacă A * k % N este 1, atunci I=k. Complexitatea este \(O(n)\).
Aplicând teorema lui Euler, \(A^{\varphi(N)} \equiv 1 (\mod N)\), unde \(\varphi(N)\) este indicatorul lui Euler. Atunci \(A \cdot A^{\varphi(N)-1} \equiv 1 (\mod N)\), deci \(I=A^{\varphi(N)-1} \mod N\). Acest rezultat poate fi determinat folosind exponențierea rapidă cu complexitatea \(O(\log_{2}N)\). Putem calcula indicatorul lui Euler cu complexitatea \(O(\sqrt{N})\), deci complexitatea determinării inversului modular devine \(O(\log_{2}N \cdot \sqrt{N})\).
Dacă N este prim, atunci \(\varphi(N) = N – 1\), deci \( I = A ^{N-2} \mod N\). Pentru determinare folosim exponențierea rapidă.
Cea mai eficientă metodă de a determina inversul modular folosește algoritmul lui Euclid extins, pentru A și N. Conform acestuia, există X și Y astfel încât A*X + N*Y = 1, deoarece 1=cmmdc(A,N), A și N fiind prime între ele. Trecând la operațiile modulo N, obținem \(A \cdot X \equiv 1 \mod N\), deoarece \(N \cdot Y \equiv 1 \mod N\). De aici rezultă că inversul modular al lui A modulo N este chiar X. Dacă X determinat astfel este negativ, îl vom mări cu N până când devine pozitiv.
Următoarea secvență C++ determină inversul modular al lui A, modulo N:
void euclid(int a , int b ,int & x ,int & y)
{
if(b == 0)
{
x = 1, y = 1;
}
else
{
int x1 , y1;
euclid(b , a % b , x1 , y1);
x = y1;
y = x1 - a / b * y1;
}
}
int main()
{
int A = 9, N = 11; // prime intre ele, 1 <= A < N
int X , Y;
euclid(A, N , X ,Y);
while(X < 0)
X += N;
cout << X; // 5
return 0;
}
Inversul modular poate fi folosit, de exemplu pentru a calcula \(C_n^k\) modulo P, unde P este un număr prim.
Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a două numere naturale are următoarea consecință: pentru două numere naturale nenule \(a\), \(b\) există numerele întregi \(x\), \(y\) astfel încât \(a \cdot x + b \cdot y = d\), unde \( d=(a,b)\) este cel mai mare divizor comun al lui \(a\) și \(b\).
Algoritmul lui Euclid se bazează pe următoarea formulă:
\( (a,b) = \begin{cases} a& \text{dacă } b = 0\\ (b,r)& \text{dacă } b \neq 0 \end{cases} \), unde \(r\) este restul împărțirii lui \(a\) la \(b\).
Analizăm cazul \(b \neq 0\). Fie \( d=(a,b)\) Conform teoremei împărțiri cu rest, există numele naturale \(c\) și \(r\), astfel încât \( a = b \cdot c + r \), unde \( 0 \leqslant r < b\).
Dacă \( d \vert a\) și \( d \vert b \) atunc \(d \vert (a-b \cdot c)\), adică \( d \vert r\). Să presupunem că există un număr \(n > d\), astfel încât \(n = (b,r)\). Atunci \( n \vert b \) și \( n \vert r \), deci \( b \vert (b \cdot c + r) \), adică \( n \vert a \). Astfel, \( n \) este divizor comun al lui \(a\) și \(b\), dar \(d\) este cel mai mare divizor comun al lui \(a\) și \(b\) – contradicție.
Următoarea funcție recursivă implementează algoritmul lui Euclid și întoarce rezultatul printr-un parametru de ieșire:
void euclid(int a , int b ,int & d)
{
if(b == 0)
d = a;
else
euclid(b , a % b , d);
}
Pentru a determina numere \(x\), \(y\) de mai sus, vom extinde funcția de mai sus, adăugându-i parametrii de ieșire x și y:
void euclid(int a , int b ,int & d, int & x ,int & y);
Determinarea valorilor lui x și y se va face astfel:
b este nul, atunci d = a și deoarece a * 1 + 0 * y = a, deducem că x=1, iar y poate lua orice valoare, de exemplu y=0;b este nenul, se determină în urma autoapelului x1 și y1 astfel încât b*x1+r*y1=d, unde r = a % b. Pe de altă parte, a = b * c + r, unde c = a / b, deci r = a - b * c. Înlocuind, obținem:
b * x1 + (a - b * c) * y1 = db * x1 + a * y1 - b * c * y1 = da * y1 + b * (x1 - c * y1) = d, unde c = a / b – câtul impărțiriia * y1 + b * (x1 - a / b * y1) = dx = y1 și y = x1 - a / b * y1Funcția următoare implementează algoritmul descris mai sus:
void euclid(int a , int b ,int & d, int & x ,int & y)
{
if(b == 0)
{
d = a;
x = 1, y = 1;
}
else
{
int x1 , y1;
euclid(b , a % b , d, x1 , y1);
x = y1;
y = x1 - a / b * y1;
}
}
Operația B/A nu poate fi realizată modulo N astfel: (B/A) % N != ((A % N)/(B % N)) % N – ușor de verificat pentru exemple concrete – deși relațiile similare au loc pentru adunare și înmulțire.
Restul împărțirii la N a lui B/A poate fi determinat, dacă A și N sunt prime între ele, prin intermediul inversului modular – dacă A și N nu sunt prime între ele, inversul modular nu există.
Mai precis, dacă 1 ≤ A < N, inversul lui A modulo N este un număr natural 1 ≤ A-1 < N cu proprietatea că \( A \cdot A^{-1} \equiv 1 \mod N \). Atunci (B/A) % N = (B * A-1) % N = ((B%N)*(A-1%N))%N.
Pentru a determina inversul modular, folosim algoritmul lui Euclid extins. Mai precis, conform algoritmului, există X și Y astfel încât A*X + N*Y = 1, deoarece 1=cmmdc(A,N), A și N fiind prime între ele. Trecând la operațiile modulo N, obtinem \(A \cdot X \equiv 1 \mod N\), deoarece \(N \cdot Y \equiv 0 \mod N\). De aici rezultă că inversul modular al lui A modulo N este chiar X. Dacă X determinat astfel este negativ, îl vom mări cu N până când devine pozitiv.
Următoarea secvență C++ determină inversul modular al lui A, modulo N:
void euclid(int a , int b ,int & x ,int & y)
{
if(b == 0)
{
x = 1, y = 1;
}
else
{
int x1 , y1;
euclid(b , a % b , x1 , y1);
x = y1;
y = x1 - a / b * y1;
}
}
int main()
{
int A = 9, N = 11; // prime intre ele, 1 <= A < N
int X , Y;
euclid(A, N , X ,Y);
while(X < 0)
X += N;
cout << X; // 5
return 0;
}
Inversul modular poate fi folosit, de exemplu pentru a calcula \(C_n^k\) modulo P, unde P este un număr prim.
Analiza combinatorică este un domeniu al matematicii care studiază modalitățile de numărare ale elementelor mulțimilor finite, precum și de alegere și aranjare a lor. Numeroase concepte specifice acestui domeniu intervin și în probleme de algoritmică.
Fie \( n \in \mathbb{N} \) și mulțimile \(A_1\), \(A_2\)., …, \(A_n\). Produsul cartezian \( A_1 \times A_2 \times … \times A_n \) este mulțimea \(n\)-uplurilor \(\left(x_1,x_2,…,x_n\right)\) cu proprietatea că \(x_1 \in A_1\), \(x_2 \in A_2\), …, \(x_n \in A_n\).
Regula produsului: Dacă mulțimile \(A_1\), \(A_2\)., …, \(A_n\) au respectiv \(k_1\), \(k_2\)., …, \(k_n\) atunci numărul de elemente al produsului cartezian \( A_1 \times A_2 \times … \times A_n \) este \(k_1 \cdot k_2 \cdot … \cdot k_n\).
Fie \(A\) o mulțimi cu n elemente. Atunci ea are \(2^n\) submulțimi:
Exemplu: Mulțimea \(A={1,2,3}\) are \(2^3 = 8\) submulțimi:
Se numește permutare o corespondență biunivocă (bijecție) între o mulțime finită și ea însăși.
Altfel spus, se numește permutare a unei mulțimi finite o aranjare a elementelor sale într-o anumită ordine.
Exemplu: permutările mulțimii {1,2,3} sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) și (3,2,1). Într-o altă reprezentare, acestea sunt:
\( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \), \( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \), \( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \), \( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \), \( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \), \( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \)
Dacă \( \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \), atunci \( \sigma(1) = 3 \), \( \sigma(2) = 1 \) și \( \sigma(3) = 2 \).
Numărul de permutări al unei mulțimi cu \(n\) elemente este \( P_n = n! = 1 \cdot 2 \cdot \cdot … \cdot n\). Acest articol conține mai multe despre factorialul unui număr.
Numărul permutărilor unei mulțimi crește foarte repede. Pentru valori mici ale lui n, numărul permutărilor depășește domeniul de valori al datelor întregi, fiind necesară implementarea operațiilor pe numere mari.
Considerăm un set de \(n\) obiecte de \(k\) tipuri. Avem \(n_1\) obiecte de tipul 1, \(n_2\) obiected e tipul 2, …, \(n_k\) obiecte de tipul k și \(n_1 + n_2 + … + n_k = n\). Numărul de permutări distincte ale celor n obiecte este:
$$ P_R(n) = \frac{n ! }{n_1 ! \cdot n_2 ! \cdot … \cdot n_k !} $$
Exemplu: Numărul de anagrame distincte ale cuvântului ABABA este:
$$ P_R(2+3) = \frac{(2+3) ! }{ 2 ! \cdot 3 ! } = \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5}{1 \cdot 2 \cdot 1 \cdot 2 \cdot 3} = 10 $$
Acestea sunt: AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA.
Dacă A este o mulțime cu n elemente, submulțimile ordonate cu k elemente ale lui A, 0 ≤ k ≤ n se numesc aranjamente a n elemente luate câte k.
Numărul de aranjamente de \(n\) luate câte \(k\) se notează \( A_{n}^{k} = n \cdot (n-1) \cdot (n-2) \cdot … \cdot (n-k+1) = \frac{ n! }{(n-k)!} \).
La fel ca în cazul permutărilor, pentru determinarea numărului de aranjamente poate fi necesară implementarea operațiilor pe numere mari.
Pentru o mulțime dată o combinare reprezintă o modalitate de alegere a unor elemente, fără a ține cont de ordinea lor. Se numesc combinări de k elemente submulțimile cu k elemente ale mulțimii, presupuse cu n elemente. Numărul de asemenea submulțimi se numește combinări de n luate câte k și se notează \(C_n^k\).
Formule:
Termenul general al acestui șir este:
$$ C_n = C_{2n}^{n} – C_{2n}^{n+1} = \frac{1}{n+1}\cdot C_{2n}^{n} = \prod _{k=2}^{n} \frac{n+k}{k}, \text{pentru } n ≥ 0 $$
O formulă recursivă:
$$ C_{n+1} = \sum_{i=0}^{n}{C_i \cdot C_{n-i}} $$
Pentru \(n=0,1,2,3,…\) numere Catalan sunt: \( 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … \).
Există numeroase probleme care au ca rezultat numerele lui Catalan. Amintim:
n paranteze deschise și n paranteze închise care se închid corect. Pentru n=3, avem \(C_3 = 5\) variante: ((())), (())(), ()(()), ()()() și (()()).2*n: formate din n caractere X și n caractere Y și în orice prefix numărul de X este mai mare sau egal cu numărul de Y. Pentru n=3: XXXYYY, XXYYXY, XYXXYY, XYXYXY, XXYXYY.n de 1 și n de -1 astfel încât toate sumele parțiale să fie nenegative.n+1 operanzi ai unei operatii asociative: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).n linii crescătoare și n linii descrescătoare. Munții încep și se termină la același nivel și nu coboară sub acel nivel: /\
/\ /\ /\/\ / \
/\/\/\ / \/\ /\/ \ / \ / \
(0,0) la (2*n,0) cu pași din {(1,1),(1,-1) care nu coboară sub axa Ox.n+2 laturi:
(0,0) la (n,n) cu pași din {(0,1),(1,0)} care nu depășesc prima diagonală \(y = x\). Următoarea imagine conține drumurile pentru n=4:n trepte folosind n dreptunghiuri. Pentru n=4:2*n puncte. Numărul posibilități de a desena n coarde care nu se intersectează este \(C_n\).Alte probleme care au care rezultat numărul lui Catalan sunt pe Wikipedia sau în documentul Exercises on Catalan and Related Numbers, Cambridge University Press, Richard P_ Stanley, June 1998.
Fie \(A={a_1, a_2, …, a_n}\) o mulțime (finită). Se numește partiție a mulțimii \(A\) o familie de submulțimi \(A_1, A_2, …, A_k\) ale lui \(A\) cu proprietățile:
De exemplu, \(A={1,2,3}\) are următoarele partiții:
Numărul de partiții cu \(k\) submulțimi ale unei mulțimi cu \(n\) elemente se numește numărul lui Stirling de speța a doua, notat \(S(n,k)\). El respectă următoarea relație de recurență:
$$ \begin{cases} S(0,0) = 1\\
S(0,n) = S(n,0) = 0\\
S(n+1,k) = k \cdot S(n,k) + S(n,k-1) & \text{pentru } k > 0 \end{cases}
$$
Numerele Strirling de speța a doua pe Wikipedia
Numărul total de partiții ale unei mulțimi cu \(n\) elemente este numărul lui Bell: $$B_n = \sum_{k=0}^n S(n,k)$$
Începând cu \(B_0 = B_1 = 1\), primele numere Bell sunt: \(1, 1, 2, 5, 15, 52, 203, 877, 4140, … \).
Numerele Bell pot fi construite cu ajutorul așa-numitului triunghi Bell. Vom construi (parțial) un tablou A[][]:
A[0][1] = 1A[i][1] = A[i-1][i]A[i][j] = A[i][j-1] + A[i-1][j-1], pentru j=2,..., i+1Bn=A[n][1].
Secvențele escape au fost folosite inițial în limbajele C/C++; în prezent sunt folosite în numeroase alte limbaje, precum Java, C# sau PHP. Ele sunt succesiuni de caractere care cu alt înțeles decât cel direct atunci când sunt folosite într-un literal caracter sau șir de caractere, fiind înlocuite cu caractere care nu ar putea fi folosite în mod direct.
Toate secvențele escape încep cu caracterul \ – numit caracter escape și conțin două sau mai multe caractere. Cele care urmează după \ definesc caracterul care va apărea în constanta literal. De exemplu, \n este o secvență escape care reprezintă caracterul newline – trecere la rând nou.
Să scriem un program care să afișeze pe ecran textul Hamlet a spus "A fi, sau a nu fi". – atenție la ghilimele! După cum știm, un literal de tip șir de caractere este delimitat cu caracterul ghilimele ", deci ar trebui să folosim o instrucțiune C++ de felul următor:
cout << "Hamlet a spus "A fi, sau a nu fi".";
Această instrucțiune este însă greșită: compilatorul identifică șirul "Hamlet a spus ", iar șirul A fi, sau a nu fi nu are înțeles sintactic! Pentru a fi corect vom folosi pentru caracterul " din șir o secvență escape, adică \":
cout << "Hamlet a spus \"A fi, sau a nu fi\".";
Mai sus, secvența escape \" este pentru caracterul " – acesta având alt înțeles pentru compilator.
| _ Secvența escape | _ Cod ASCII | _ Caracter |
|---|---|---|
\a |
7 |
Alertă, Beep |
\b |
8 |
Backspace |
\e |
27 |
Escape |
\f |
12 |
Formfeed |
\n |
10 |
NewLine |
\r |
13 |
Carriage Return |
\t |
9 |
Tab orizontal |
\v |
11 |
Tab vertical |
\\ |
92 |
Backslash |
\" |
34 |
Ghilimele |
\' |
39 |
Apostrof |
\? |
63 |
Semn de întrebare |
\0 |
0 |
Caracterul nul, cu înțeles special în șirurile de caractere |
\nnn |
oricare | Caracterul cu codul egal cu valoarea octală nnn |
\xhh |
oricare | Caracterul cu codul egal cu valoarea hexazecimală hh |
Există de asemenea secvențe escape pentru reprezentarea caracterelor non ASCII.
Utilizarea ghilimelelor într-un șir de caractere
#include <iostream>
using namespace std;
int main()
{
cout << "Hamlet a spus \"A fi, sau a nu fi\".";
return 0;
}

Trecerea la rând nou
#include <iostream>
using namespace std;
int main()
{
cout << "Vrei 10 la info?\nHai pe pbinfo";
return 0;
}

Secvența escape poate fi folosită într-un caracter (ex. '\n') sau într-un șir de caractere (ex. "\n"). Următoarele două programe au același efect ca cel de mai sus:
#include <iostream>
using namespace std;
int main()
{
cout << "Vrei 10 la info?" << "\n" << "Hai pe pbinfo";
return 0;
}
#include <iostream>
using namespace std;
int main()
{
cout << "Vrei 10 la info?" << '\n' << "Hai pe pbinfo";
return 0;
} Ciurul lui Eratostene este o metodă rapidă prin care stabilește despre fiecare număr natural mai mic sau egal cu un n dat dat este prim sau nu. Valoarea lui n trebuie să fie suficient de mică pentru a putea declara un tablou P cu n+1 elemente, un element P[k] având valoarea 1 dacă k este prim, respectiv valoarea 0 dacă k nu este prim.
Următoarea secvență C++ construiește tabloul P[]:
int P[n+1];
for(int i = 0 ; i <= n ; i ++)
P[i] = 1;
P[0] = P[1] = 0;
for(int i = 2 ; i * i <= n ; i ++)
if(P[i] == 1)
for(int j = 2 ; i * j <= n ; j ++)
P[i * j] = 0;
Ideea de mai sus poate fi utilizată pentru a determina diverse rezultate în care intervin divizorii unui număr, rezultate calculate pentru toate numerele mai mici sau egale cu n:

Nr[]. La final, Nr[x] va fi numărul de divizori ai lui x;Nr[] cu 0;Nr[i] mărim valorile elementelor Nr[k], unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie numărat ca atare.int Nr[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
Nr[i] = 0;
for(int i = 1; i <= DIM ; i ++)
for(int j = 1 ; i * j <= DIM ; j ++)
Nr[i * j] ++;
OBS: Un număr x este prim dacă și numai dacă la final Nr[x] este egal cu 2.
S[]. La final, S[x] va reprezenta suma divizorilor lui x;S[] cu 0;S[i] mărim valorile elementelor S[k] cu i, unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie adunat la suma divizorilor lui k.int S[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
S[i] = 0;
for(int i = 1; i <= DIM ; i ++)
for(int j = 1 ; i * j <= DIM ; j ++)
S[i * j] += i;
OBS: Un număr x este prim dacă și numai dacă la final S[x] este egal cu x+1.
M[]. La final, M[x] va reprezenta cel mai mic divizor (factor) prim al lui x;M[x] cu x – pentru numerele prime cel mai mic factor prim sunt ele însele;2 și pentru fiecare număr i prim (pentru care M[i] = i) modificăm, dacă este cazul, cel mai mic factor prim pentru toți multipli k = i * j lui i.int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
M[i] = i;
for(int i = 2; i <= DIM ; i ++)
if(M[i] == i)
for(int j = 2 ; i * j <= DIM ; j ++)
if(M[i * j] == i * j)
M[i * j] = i;
OBS:
x este prim dacă și numai dacă la final M[x] este egal cu x.i, vom modifica multiplul k = i * j numai dacă M[k] este încă k. De exemplu, pentru i=3, nu-l mai modifică pe M[6] – a fost deja modificat pentru i=2.M[k] de pentru fiecare i, deoarece i este considerat în ordine crescătoare, la final M[k] va memora cel mai mare divizor prim al lui k. Următoarea secvență obține acest rezultat – observați că modificările sunt minore:int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
M[i] = i;
for(int i = 2; i <= DIM ; i ++)
if(M[i] == i)
for(int j = 2 ; i * j <= DIM ; j ++)
M[i * j] = i;
Indicatorul lui Euler este tratat în acest articol. Reluăm aici numai secvența C/C++:
int F[DIM + 1];
for(int i =1 ; i <= DIM ; i ++)
F[i] = i;
for(int i = 2; i <= DIM ; i ++)
if(F[i] == i)
{
for(int j = 1 ; j * i <= DIM ; j ++)
F[j * i]= F[j * i] / i * (i - 1);
}
OBS: Un număr x este prim dacă și numai dacă la final F[x] este egal cu x-1.
Încercați să determinați în același mod:
Operațiile pe biți, descrise aici sunt foarte rapide și au o serie de aplicații utile în practică. Acesta articol prezintă o parte dintre ele, limbajul de programare folosit fiind C/C++.
Reamintim faptul că biții din reprezentarea internă a unui număr întreg se numerotează începând de la 0, de la dreapta spre stânga.
2Înmulțirea cu o puterea lui 2 se face foarte rapid cu operația de deplasare la stânga pe biți, <<. Astfel, a * 2k este egal cu a << k. Desigur, atenție la overflow!
2Câtul împărțirii poate fi determina prin deplasarea la dreapta, >>. Astfel, a / 2k este egal cu a >> k.
Reprezentarea în baza 2 a unui număr par (și reprezentarea sa internă) se termină cu cifra 0, iar a unui număr impar se termină cu 1. Atunci, deoarece reprezentarea lui 1 are un singur bit 1, restul fiind 0, operația n & 1 are rezultat:
0, dacă n este par1, dacă n este imparÎN general n & 1 reprezintă ultimul bit din reprezentarea internă a lui n.
2Puterile lui 2 au un singur bit 1, ceilalți fiind 0. Mai clar, 2k are doar bitul k egal cu 1, ceilalți fiind 0. În plus, 2k-1 are toate cifrele binare 1 – de fapt, primele k cifre (de la dreapta) sunt 1, celelalte fiind 0. Observăm că aplicăm operația & între 2k și 2k-1 vom obține 0.
Pentru a verifica dacă un număr natural oarecare n este putere a lui 2, calculăm expresia n & (n-1). Rezultatul său este 0 dacă și numai dacă n este putere a lui 2.
În general, n & (n-1) are ca rezultat valoarea lui n în care ultimul bit 1 a fost transformat în 0. Dacă n este putere a lui 2, în rezultatul expresiei anterioare singurul bit 1 al lui n devine 0, deci rezultatul este 0.
2 care îl divide pe nEste egală cu 2 la puterea numărul de biți 0 de la sfârșitul reprezentării în baza 2 a lui n. Acest număr poate fi determinat rapid ca rezultat al expresiei n & -n. Analizați reprezentările interne a lui n și a lui -n pentru a înțelege mai bine!
1Fie n un număr întreg (de regulă natural), iar k un număr natural. Ne propunem să transformăm bitul k al lui n în 1, operație numită și setare a bitului k, ceilalți biți rămânând nemodificați – considerăm că valoarea lui k este mai mică decât numărul de cifre binare din reprezentarea internă a lui n (16 pentru short și unsigned short, 32 pentru int și unsigned int, etc.).
Transformarea unui bit în 1, precum și următoarele doua aplicații din acest articol (transformarea unui bit în 0 și determinarea valorii unui bit) se fac aplicând o anumită operație pe biți între numărul n și o mască, determinată convenabil pe baza valorii lui k.
În cazul transformării bitului k în 1, masca va avea doar bitul k egal cu 1, restul biților fiind 0. Astfel, masca este 1 << k, iar operația este n | (1 << k). Rezultatul ei are aceeași reprezentare internă ca n, cu excepția bitului k, care este transformat în 1; dacă bitul k era de la început 1, el nu se va modifica.
Mai precis, setarea bitului k se face prin următoarea atribuire: n = n | (1 << k);.
0Transformarea bitului k a lui n în 0, numită și resetarea bitului k, se face folosind o mască în care toți biții sunt 1, cu excepția bitului k sunt 1, bitul k fiind 0. Această mască este: ~(1 << k), ~ fiind operația de complementare a biților.
Atunci, resetarea bitului k a lui n se poate face cu atribuirea: n = n & ~(1 << k);.
Pentru a determina bitul k al lui n putem folosi expresia (n >> k) & 1. Prin operația n >> k se elimină ultimele k cife binare ale lui n, iar (n >> k) & 1 reprezintă ultimul bit al lui n >> k, deci bitul k al lui n.
O altă variantă ar fi să folosim masca 1 << k, prin operația n & (1 << k). Rezultatul acestei operații este 0, dacă bitul k este 0, respectiv 2k (adică 1 << k), dacă bitul k este 1.
^Disjuncția exclusivă are o proprietate interesantă, și anume că n ^ n este 0, indiferent de valoarea lui n. Acest lucru are câteva consecințe:
a ^ b ^ b este egal cu a. Putem realizat astfel un mecanism de cripare:
n un număr care trebuie criptat și k un număr care reprezintă cheia de criptare;n ^ k, prin care obținem numărul criptat c;c ^ k, prin care obținem numărul inițial n;x și una singură apare de un număr impar de ori (celelalte apărând de număr par de ori), o putem determina calculând suma XOR a numerelor x, adică:
S = 0;x
S ^= x;S.a și b, fără a folosi o variabilă suplimentară:
a = a ^ b;b = a ^ b;a = a ^ b;
Problemă: Se dă o matrice binară, reprezentând harta unui teren (labirint, clădire, tablă de joc, etc.), în care valorile 0 reprezintă zone libere, iar cele egale cu 1 reprezintă obstacole. Într-o zonă aflată la coordonate cunoscute se află un mobil, care se poate deplasa prin matrice, trecând din zona curenta în una din cele patru zone vecine de pe aceeași linie sau aceeași coloană, dacă este liberă. Să se identifice zonele în care poate să ajungă mobilul.
Problema enunțată mai sus face parte din categoria Algoritmilor de umplere sau FILL, iar prezentul articol este consacrat acestor algoritmi!
