Algortimi Utili

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