Algoritmi Fundamentali pentru Clasa a XI-a

Algoritmi fundamentali de bază

Să începem cu funcții care procesează cifrele unui număr. Aceste funcții sunt esențiale pentru rezolvarea multor probleme de algoritmi.

Funcția suma_cif() calculează suma cifrelor unui număr. Aceasta folosește operația %10 pentru a extrage ultima cifră și /10 pentru a elimina cifra respectivă:

int suma_cif(int x) {
    int S = 0;
    while(x > 0) {
        S = S + x % 10;
        x = x / 10;
    }
    return S;
}

Funcția prod_cif_pare() calculează produsul cifrelor pare ale unui număr. Observă cum verificăm dacă cifra este pară cu condiția if(n%10%2==0):

int prod_cif_pare(int n) {
    int p = 1;
    if(n == 0) p = 0;
    while(n > 0) {
        if(n%10%2 == 0)
            p = p*(n%10);
        n = n/10;
    }
    return p;
}

💡 Sfat util: Pentru a verifica dacă un număr este par, folosește operatorul modulo: numar % 2 == 0. Acest operator va fi esențial în multe algoritmi!

De asemenea, un algoritm fundamental este interschimbarea valorilor a două variabile. Pentru aceasta, avem nevoie de o variabilă auxiliară:

void interschimbare(int &x, int &y) {
    int aux;
    aux = x;
    x = y;
    y = aux;
}

Oglindirea unui număr și operații cu cifre

Când avem nevoie să inversăm cifrele unui număr, folosim algoritmul de oglindire. Este un algoritm util pentru verificarea palindroamelor sau pentru transformări numerice.

Iată algoritmul pentru a obține oglinditul unui număr:

long ogl_numar(long a) {
    long ogl = 0;
    while(a > 0) {
        ogl = ogl * 10 + (a % 10);
        a = a / 10;
    }
    return ogl;
}

Pentru a găsi cifra minimă dintr-un număr, parcurgem toate cifrele și păstrăm valoarea minimă întâlnită:

long cif_mini(long x) {
    long mini = x % 10;
    while(x > 0) {
        if((x % 10) < mini)
            mini = x % 10;
        x = x / 10;
    }
    return mini;
}

Un algoritm interesant este eliminarea cifrelor pare dintr-un număr. Construim un nou număr care conține doar cifrele impare din numărul original:

int eliminare(int n) {
    int p = 1, m = 0;
    while(n > 0) {
        if(n % 2 == 1) {  // dacă ultima cifră e impară
            m = m + (n % 10) * p;
            p = p * 10;
        }
        n = n / 10;
    }
    return m;
}

💡 Reține: Când construiești un număr din cifre individuale, folosești formula numar = numar * 10 + cifra pentru a adăuga cifre la dreapta, sau numar = cifra * putere + numar (cu putere = 10, 100, etc.) pentru a adăuga la stânga.

Transformări numerice și algoritmi matematici

Dublarea cifrelor pare este un algoritm util care construiește un nou număr dublând apariția cifrelor pare din numărul original:

long dublare(long n) {
    long p = 1;
    long nr = 0;
    while(n > 0) {
        if(n % 10 % 2 == 0) {  // dacă cifra e pară
            nr = nr + (n % 10) * p;
            p = p * 10;
        }
        nr = nr + (n % 10) * p;
        p = p * 10;
        n = n / 10;
    }
    return nr;
}

Conversia unui număr în baza 2 (binar) este un algoritm fundamental în informatică:

long baza2(long n) {
    long p = 1, nr = 0;
    while(n != 0) {
        nr = nr + (n % 2) * p;
        p = p * 10;
        n = n / 2;
    }
    return nr;
}

Calculul celui mai mare divizor comun (CMMDC) folosind algoritmul lui Euclid poate fi implementat în două moduri:

1. Prin scăderi repetate:

void cmmdc(int a, int b) {
    while(a != b) {
        if(a > b)
            a = a - b;
        else 
            b = b - a;
    }
    cout << a;  // a este CMMDC-ul
}

2. Prin împărțiri repetate (mai eficient):

long cmmdc(long a, long b) {
    long r;
    while(b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

💡 Important: Metoda cu împărțiri repetate este mult mai eficientă decât cea cu scăderi, mai ales pentru numere mari. Încearcă să o folosești de fiecare dată când calculezi CMMDC!

Calculul CMMMC și algoritmi pentru divizori

Cel mai mic multiplu comun (CMMMC) poate fi calculat folosind relația cu CMMDC:

void cmmmc(long a, long b) {
    long p = a * b;
    while(a != b) {
        if(a > b)
            a = a - b;
        else 
            b = b - a;
    }
    p = p / a;  // p / CMMDC(a,b)
    cout << p;
}

Pentru a calcula numărul de divizori ai unui număr, putem folosi o metodă directă:

long nr_div(long a) {
    long nr = 0;
    for(long i = 1; i <= a; i++)
        if(a % i == 0)
            nr++;
    return nr;
}

Un algoritm mai eficient pentru numere mari este calculul numărului de divizori folosind descompunerea în factori primi:

void nr_div(long a, long &nr) {
    nr = 1;
    int p = 0, d = 2;
    while(a != 1) {
        if(a % d == 0) {
            p = 0;
            while(a % d == 0) {
                p++;
                a = a / d;
            }
            nr = nr * (p + 1);
        }
        d++;
        if(d * d > a)
            d = a;
    }
}

Suma divizorilor primi ai unui număr se poate calcula astfel:

int suma_div(int n) {
    int d = 2;
    int s = 0;
    while(n != 1) {
        if(n % d == 0) {
            s = s + d;
            while(n % d == 0)
                n = n / d;
        }
        d++;
        if(d * d > n)
            d = n;
    }
    return s;
}

💡 Optimizare: Condiția if(d * d > n) este o optimizare importantă pentru algoritmi care lucrează cu factori primi. Aceasta îți permite să sari direct la ultimul factor prim dacă acesta există.

Descompuneri, verificări și șiruri speciale

Descompunerea în factori primi este fundamentală în teoria numerelor:

void desc(int n) {
    int p, i;
    for(i = 2; i <= n; i++) {
        if(n % i == 0) {
            p = 0;
            while(n % i == 0) {
                n = n / i;
                p++;
            }
            cout << i << "^" << p << endl;
        }
    }
}

Pentru verificarea unui număr prim, folosim definiția: un număr este prim dacă are exact 2 divizori (1 și el însuși):

long nrprim(long n) {
    long nr = 0, i;
    for(i = 1; i <= n; i++)
        if(n % i == 0)
            nr++;
    if(nr == 2 && n >= 2)
        return 1;
    else
        return 0;
}

O metodă eficientă pentru a afișa factorii primi cu putere pară ai unui număr:

void fac_primi(long n) {
    long p = 0, i;
    for(i = 2; i <= n; i++) {
        p = 0;
        while(n % i == 0) {
            n = n / i;
            p++;
        }
        if(p % 2 == 0 && p > 0)
            cout << i << endl;
    }
}

Generarea șirului Fibonacci este un algoritm clasic și util:

void fib(long n) {
    long a = 1, b = 1, c;
    cout << a << " " << b << " ";
    for(int i = 3; i <= n; i++) {
        c = a + b;
        cout << c << " ";
        a = b;
        b = c;
    }
}

💡 Aplicații practice: Algoritmii de verificare a primalității și descompunerile în factori primi sunt esențiali în criptografie și securitatea informatică. Șirul Fibonacci apare în numeroase fenomene naturale și probleme de optimizare!

Tehnici avansate și implementări alternative

Când lucrezi cu funcții în C++, există trei moduri principale de a returna valori:

1. Prin returnare directă - folosind return:

int suma_cif(int x) {
    // calcul...
    return S;
}

2. Prin afișare - funcția afișează direct rezultatul:

void suma_cif(int x) {
    // calcul...
    cout << S;
}

3. Prin parametru de ieșire - folosind referințe (&):

void suma_cif(int x, int &S) {
    S = 0;
    // calcul...
}

Optimizarea algoritmilor este esențială pentru eficiență. De exemplu, pentru verificarea primalității, o versiune optimizată ar fi:

bool estePrim(long n) {
    if(n < 2) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    
    for(long i = 3; i*i <= n; i += 2)
        if(n % i == 0)
            return false;
    return true;
}

Când implementezi algoritmi recursivi, fii atent la condițiile de bază. De exemplu, Fibonacci recursiv:

long fibonacci(long n) {
    if(n <= 2) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

💡 Sfat de optimizare: Recursivitatea este elegantă, dar poate duce la probleme de performanță pentru valori mari. Pentru algoritmi precum Fibonacci, implementările iterative sunt de obicei mai eficiente.

Experimentează cu acești algoritmi fundamentali - ei formează baza pentru rezolvarea problemelor mai complexe în informatică!