Articole recomandate

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.

Descrierea algoritmului

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:

• se ordonează muchiile grafului crescător după cost;
• se analizează pe rând muchiile grafului, în ordinea crescătoare a costurilor;
• pentru fiecare muchie analizată:
  • dacă extremitățile muchiei fac parte din același subarbore, muchia se ignoră
  • dacă extremitățile muchiei fac parte din subarbori diferiți, aceștia se vor reuni, iar muchia respectivă face parte din APM.

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.

Exemplu

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

Secvență C++

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;
}

Vezi și

• Algoritmul lui Prim

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.

Etapele lucrului cu fișiere text

În C++ există mai multe modalități de lucru cu fișiere text. Toate respectă următoarele etape:

1. deschiderea fișierului/asocierea fișierului cu un flux de date;
2. citirea din fișier/scrierea în fișier;
3. închiderea fișierului/fluxului de date

Deschiderea fișierului

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ă.

Citirea din fișier/scrierea în fișier

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;

Închiderea fișierelor

Se face astfel:

fin.close();
fout.close();

Un exemplu complet

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;
}

Observații

• fișierele de intrare (deschise pentru citire) trebuie să existe. Dacă se deschide pentru citire un fișier care nu există, operațiile de citire (fin >> ...) vor eșua și comportamentul programului devine de multe ori impredictibil;
• fișierele de ieșire (deschise pentru scriere) nu trebuie să existe. La deschidere ele vor fi create. Dacă fișierul de ieșire există conținurul său va fi înlocuit cu datele scrise de programul care rulează.

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;
}

Descriere

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}$$

Exemplu

Să calculăm \(2^{25}\):

• \(2^{25} = 2 \cdot 2^{24}\), deoarece 25 este impar
• \(2^{24} = {(2^{12})}^2\), deoarece 24 este par
• \(2^{12} = {(2^{6})}^2\), deoarece 12 este par
• \(2^{6} = {(2^{3})}^2\), deoarece 6 este par
• \(2^{3} = 2 \cdot 2^{2}\), deoarece 3 este impar
• \(2^{2} = {(2^{1})}^2\), deoarece 2 este par
• \(2^{1} = 2 \cdot 2^{0}\), deoarece 1 este impar
• \(2^{0} = 1\)

Atunci în ordine inversă:

• \(2^{1} = 2 \cdot 1 = 2\)
• \(2^{2} = {2}^2 = 4\)
• \(2^{3} = 2 \cdot 4 = 8\)
• \(2^{6} = {8}^2 = 64\)
• \(2^{12} = {64}^2 = 4096\)
• \(2^{24} = {4096}^2 = 16777216\)
• \(2^{25} = 2 \cdot 16777216 = 33554432\)

Constatăm că numărul înmulțirilor efectuate este mult mai mic decât în cazul primei metode.

Implementare recursivă

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;
}

Implementare iterativă

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:

• vom determina un produs P, format din factori de forma A1, A2, A4, A8, …
• determinăm cifrele reprezentării în baza 2 a lui n, începând cu cea mai nesemnificativă:
  • dacă cifra curentă este 1, înmulțim pe A la P, P = P * A;
  • înmulțim pe A cu el însuși, A = A * A;, obținând următoarea putere din șirul de mai sus

Implementare 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;
}

Observații

• ridicarea la putere rapidă poate fi folosită și pentru:
  • operații modulo (determinarea restului împărțirii rezultatului la o valoare dată)
  • numere mari
  • ridicarea la putere a matricelor
  • ridicarea la putere a polinoamelor

Î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\).

Adunarea și înmulțirea

Avem următoarele reguli – spunem că congruența modulo N este compatibilă cu adunarea și înmulțirea numerelor întregi :

• Dacă \( a \equiv x \mod N \) și \( b \equiv y \mod N \), atunci \( a + b \equiv x + y \mod N \).
• Dacă \( a \equiv x \mod N \) și \( b \equiv y \mod N \), atunci \( a \cdot b \equiv x \cdot y \mod N \).

Consecințe (C/C++):

• având două numere naturale a, b, iar N > 1 unu număr natural:
  • restul împărțirii sumei la N este (a + b) % N = (a % N + b % N) % N
  • restul împărțirii produsului la N este (a * b) % N = ((a % N) * (b % N)) % N
• având n 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;

• pentru a calcula restul împărțirii la N a lui N! – N factorial:

int P = 1;
for(int i =1 ; i <= N ; i ++)
    P = (P * i) % N;

Scăderea

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;

Împărțirea. Inversul modular

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

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);
}

Algoritmul extins

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:

• dacă 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;
• dacă 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 = d
  • b * x1 + a * y1 - b * c * y1 = d
  • a * y1 + b * (x1 - c * y1) = d, unde c = a / b – câtul impărțirii
  • a * y1 + b * (x1 - a / b * y1) = d
  • deci x = y1 și y = x1 - a / b * y1

Funcț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;
    }
}

Invers modular

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ă.

Produsul cartezian

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\).

Submulțimile unei multimi

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:

1. \( \emptyset \)
2. \(\left\{1\right\}\), \(\left\{ 2 \right\}\), \(\left\{ 3 \right\}\)
3. \(\left\{1,2\right\}\), \(\left\{1,3\right\}\), \(\left\{2,3\right\}\)
4. \(\left\{1,2,3\right\}\)

Permutări

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.

Permutări cu repetiție

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.

Aranjamente

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.

Combinări

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:

• \(C_n^k = \frac{A_n^k}{P_k}\)
• \(C_n^k = \frac{n \cdot (n-1) \cdot … \cdot (n-k+1)}{1 \cdot 2 \cdot … \cdot k}\)
• \(C_n^k = \frac{n!}{k!\cdot {(n-k)!}} \)
• \(C_n^k= \begin{cases}
  1& \text{dacă } k = 0,\\
  \frac{n – k + 1}{k} \cdot { C_n^k } & \text{altfel}.
  \end{cases} \)
• \(C_n^k= \begin{cases}
  1& \text{dacă } n = k \text{ sau } k = 0,\\
  { C_{n-1}^{k-1} } + { C_{n-1}^k } & \text{altfel}.
  \end{cases} \); această formulă se regăsește în Triunghiul lui Pascal

Numerele lui Catalan

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:

• \(C_n\) este egal cu numărul de șiruri de n paranteze deschise și n paranteze închise care se închid corect. Pentru n=3, avem \(C_3 = 5\) variante: ((())), (())(), ()(()), ()()() și (()()).
• numărul de cuvinte Dyck de lungime 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.
• numărul de șiruri formate din n de 1 și n de -1 astfel încât toate sumele parțiale să fie nenegative.
• \(C_n\) reprezintă numărul de modalități de a paranteza o expresie formată din n+1 operanzi ai unei operatii asociative: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
• \(C_n\) reprezintă numărul de modalităti de a desena “șiruri de munți” cu 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:

                                            /\
           /\          /\       /\/\       /  \
/\/\/\    /  \/\    /\/  \     /    \     /    \

• numărul de drumuri laticiale de la punctul (0,0) la (2*n,0) cu pași din {(1,1),(1,-1) care nu coboară sub axa Ox.
• \(C_n\) este numărul de modalități de a triangula un poligon cu n+2 laturi:

• \(C_n\) este umărul de drumuri laticiale de la (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:

• numărul de siruri \( 1 \leqslant a_1 \leqslant a_2 \leqslant … \leqslant a_n \) cu proprietatea că \(a_k \leqslant k \) este \(C_n\).
• \(C_n\) numărul de modalități de a acoperi o scară cu n trepte folosind n dreptunghiuri. Pentru n=4:

• pe un cerc sunt 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.

Partițiile unei mulțimi

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:

1. \( A_i \subseteq A \), \( \forall i = \overline{1,k} \)
2. \( A_1 \cup A_2 \cup … \cup A_k = A \)
3. \( A_i\cap A_j = \emptyset \), \( \forall i\neq j \)

De exemplu, \(A={1,2,3}\) are următoarele partiții:

• \({1,2,3}\)
• \({1,2},{3}\), \({1,3},{2}\), \({1}, {2,3}\)
• \({1},{2},{3}\)

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] = 1
• primul element de pe liniile următoare este egal cu ultimul de pe linia precedentă: A[i][1] = A[i-1][i]
• celelalte elemente ale fiecărei linii sunt egale cu suma celor după elemnte din stânga (linia curentă și linia precedentă): A[i][j] = A[i][j-1] + A[i-1][j-1], pentru j=2,..., i+1
• primul elelemt de pe fiecare linie este numărul Bell corespunzător: Bn=A[n][1].

Numerele Bell pe Wikipedia

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.

De ce sunt necesare?

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.

Lista secvențelor escape

Există de asemenea secvențe escape pentru reprezentarea caracterelor non ASCII.

Exemple

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:

• numărul de divizori
• suma divizorilor
• cel mai mic divizor prim
• cel mai mare divizor prim
• indicatorul lui Euler

Numărul de divizori

• construim un vector Nr[]. La final, Nr[x] va fi numărul de divizori ai lui x;
• inițializăm elementele vectorului Nr[] cu 0;
• parcurgem vectorul și pentru fiecare element 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.

Suma divizorilor

• construim un vector S[]. La final, S[x] va reprezenta suma divizorilor lui x;
• inițializăm elementele vectorului S[] cu 0;
• parcurgem vectorul și pentru fiecare element 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.

Cel mai mic/mare divizor prim

• construim un vector M[]. La final, M[x] va reprezenta cel mai mic divizor (factor) prim al lui x;
• inițializăm elementele vectorului M[x] cu x – pentru numerele prime cel mai mic factor prim sunt ele însele;
• parcurgem numerele începând de la 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:

• Un număr x este prim dacă și numai dacă la final M[x] este egal cu x.
• La parcurgerea multiplilor lui 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.
• Dacă modificăm 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

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.

Alte probleme

Încercați să determinați în același mod:

• numărul factorilor primi
• suma/produsul factorilor primi
• etc.

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.

Înmulțirea cu puteri ale lui 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!

Împărțirea cu puteri ale lui 2

Câtul împărțirii poate fi determina prin deplasarea la dreapta, >>. Astfel, a / 2k este egal cu a >> k.

Verificarea parității unui număr

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 par
• 1, dacă n este impar

ÎN general n & 1 reprezintă ultimul bit din reprezentarea internă a lui n.

Verificarea faptului că un număr este putere a lui 2

Puterile 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.

Cea mai mare putere a lui 2 care îl divide pe n

Este 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!

Transformarea unui bit în 1

Fie 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);.

Transformarea unui bit în 0

Transformarea 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);.

Determinarea valorii unui bit

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.

Proprietăți ale disjuncției exclusive ^

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:
  • fie n un număr care trebuie criptat și k un număr care reprezintă cheia de criptare;
  • pentru criptare folosim operația n ^ k, prin care obținem numărul criptat c;
  • pentru decriptare folosim operația c ^ k, prin care obținem numărul inițial n;
• dacă avem mai multe valori 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;
  • pentru fiecare x
    • S ^= x;
  • rezultatul este S.
• putem interschimba valorile a două variabile 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!