Algoritm de sortare (Selection Sort)
void sort(int v[], const int l)
{
for (int i = 1; i < l; i++)
{
// Ca sa sortati descrescator folositi v[j] > v[j-1]
for (int j = i; j >= 0 && v[j] < v[j-1]; j--)
{
int tmp = v[j];
v[j] = v[j-1];
v[j-1] = tmp;
}
}
}
Cel mai mare divizor comun
int cmmdc(int a, int b)
{
int t;
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
Cel mai mic multiplu comun
int cmmmc(int a, int b)
{
return (a * b) / cmmdc(a, b);
}
Primalitatea unui număr
#include <cmath>
bool estePrim(int n)
{
for (int i = 2; i <= sqrt(n); i++)
// Daca i divide n, inseamna ca i este divizor al lui n,
// deci n nu este prim
if (n % i == 0) return false;
// Daca am ajuns aici inseamna ca n este prim
return true;
}
Căutarea Binară
// *** Binary Search *** //
// d (dreapta) - limita inferioara
// s (stanga) - limita superioara
// key - elementul cautat
// v - vectorul SORTAT in care se face cautarea
int binary_search(int d, int s, int key, int * v)
{
if (s < d) return -1; // Nu s-a gasit nicio valoare
int m = (d + s) / 2; // Elementul din mijloc
if (key < v[m]) return binary_search(d, m-1, key, v); // Cauta in subvectorul din stanga
else if (key > v[m]) return binary_search(m+1, s, key, v); // Cauta in subvectorul din dreapta
else return m; // Gasit! Returneaza indicele
}
Versiunea iterativă
int binary_search(int d, int s, int key, int * v)
{
while (s >= d)
{
int m = (d + s) / 2;
if (key < v[m])
s = m - 1;
else if (key > v[m])
d = m + 1;
else
return m;
}
return -1;
}
Niciun comentariu:
Trimiteți un comentariu
Rețineți: Numai membrii acestui blog pot posta comentarii.