Introducere în Algoritmi de Bază în C++ pentru Clasa a IX-a

Algoritmi de bază în C++

Te-ai întrebat vreodată cum să afli rapid minimul, maximul sau să ordonezi trei numere? E mai simplu decât crezi!

Iată un program care citește trei numere naturale și afișează minimul, maximul și ordonarea lor crescătoare:

#include <iostream>
using namespace std;
int main() {
    int x, y, z, Min, Max, s;
    cin >> x >> y >> z;
    s = x + y + z;
    Min = Max = x;
    
    if (y < Min) Min = y;
    if (z < Min) Min = z;
    if (y > Max) Max = y;
    if (z > Max) Max = z;
    
    cout << "Min= " << Min;
    cout << "Max= " << Max;
    cout << "Ordonarea crescătoare este: ";
    cout << Min << " " << s-(Min+Max) << " " << Max;
    return 0;
}

💡 Trucul inteligent: Observă cum aflăm numărul din mijloc folosind suma totală din care scădem minimul și maximul!

Algoritmi pentru CMMDC

Calcularea celui mai mare divizor comun (CMMDC) este utilă în multe probleme. Avem două metode principale:

Metoda 1: Algoritmul lui Euclid folosește împărțiri succesive pentru a găsi CMMDC:

#include <iostream>
using namespace std;
int main() {
    int a, b, r, aux, m;
    cin >> a >> b;
    
    if (a < b) {
        aux = a; a = b; b = aux;
    }
    m = a * b;
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    cout << b; // CMMDC este b
    return 0;
}

Metoda 2: Prin scăderi repetate este o alternativă intuitivă:

#include <iostream>
using namespace std;
int main() {
    int n, d;
    cin >> n >> d;
    while (n != d) {
        if (n > d) n = n - d;
        else d = d - n;
    }
    cout << "cmmdc= " << d;
    return 0;
}

💡 Reține: Algoritmul lui Euclid prin împărțiri este mai eficient pentru numere mari decât metoda scăderilor repetate!

Calculul CMMMC și CMMDC pentru mai multe numere

Cel mai mic multiplu comun (CMMMC) se calculează ușor folosind relația cu CMMDC:

#include <iostream>
using namespace std;
int main() {
    int n, d, p;
    cin >> n >> d;
    p = n * d;
    
    while (n != d) {
        if (n > d) n = n - d;
        else d = d - n;
    }
    
    cout << "cmmmc= " << p/d;
    return 0;
}

Pentru calculul CMMDC a mai multor numere dintr-un șir (până la întâlnirea lui 0), folosim proprietatea asociativă, calculând succesiv:

#include <iostream>
using namespace std;
int main() {
    int n, d, a, b;
    cin >> a;
    
    if (a != 0) {
        d = a;
        cin >> a;
        
        while (a != 0) {
            b = d;
            
            while (a != b) {
                if (a > b) a = a - b;
                else b = b - a;
            }
            
            d = a;
            cin >> a;
        }
        
        cout << "cmmdc = " << d;
    } else {
        cout << "cmmdc = 0";
    }
    return 0;
}

💡 Indiciu: CMMDC(a,b,c) = CMMDC(CMMDC(a,b),c) - aplicăm algoritmul în perechi succesive!

Implementări alternative pentru CMMDC

Iată o variantă alternativă pentru calculul CMMDC al mai multor numere citite până la întâlnirea valorii 0:

#include <iostream>
using namespace std;
int main() {
    int a, b, D;
    cin >> a;
    
    if (a != 0) {
        D = a;
        cin >> a;
        
        while (a != 0) {
            b = D;
            
            while (a != b) {
                if (a > b)
                    a = a - b;
                else
                    b = b - a;
            }
            
            D = a;
            cin >> a;
        }
        
        cout << "cmmdc=" << D;
    } else {
        cout << "cmmdc=" << 0;
    }
    return 0;
}

Această implementare citește numere succesive și actualizează CMMDC la fiecare pas. Practic, calculăm CMMDC(CMMDC(numerele anterioare), numărul curent).

💡 Observație: Este esențial să verificăm dacă primul număr citit este 0, pentru a evita calcule inutile!

Identificarea numerelor prime

Un număr prim are exact doi divizori: 1 și el însuși. Iată cum putem găsi numerele prime dintr-un șir de valori:

Metoda 1: Verificare eficientă până la rădăcina pătrată

#include <iostream>
using namespace std;
int main() {
    int n, ok, d;
    cin >> n;
    
    ok = 1; // presupunem că n este prim
    d = 2;
    
    while (d*d <= n && ok == 1) {
        if (n % d == 0)
            ok = 0; // am găsit un divizor, n nu e prim
        d = d + 1;
    }
    
    if (ok == 1 && n > 1)
        cout << n << " este prim";
    else
        cout << n << " nu este prim";
    
    return 0;
}

Această metodă verifică dacă numărul n este prim testând divizibilitatea doar până la rădăcina pătrată a lui n, ceea ce optimizează semnificativ algoritmul.

💡 Trucul eficienței: Nu trebuie să verificăm toți divizorii până la n, ci doar până la √n. Dacă n nu are divizori până la √n, atunci e prim!

Identificarea tuturor numerelor prime dintr-un șir

Pentru a găsi toate numerele prime dintr-un șir de valori citite până la întâlnirea lui 0:

#include <iostream>
using namespace std;
int main() {
    int nr, a;
    bool exist = false;
    cin >> a;
    
    while (a != 0) {
        // verificăm dacă a este prim
        nr = 0;
        for (int d = 1; d <= a; d++)
            if (a % d == 0)
                nr++;
                
        if (nr == 2) {
            exist = true;
            cout << a << " ";
        }
        
        cin >> a;
    }
    
    if (exist == false)
        cout << "Nu există numere prime în șir";
    
    return 0;
}

Această metodă numără toți divizorii fiecărui număr din șir. Un număr este prim dacă are exact doi divizori (1 și el însuși).

💡 Sfat de optimizare: Deși această metodă e ușor de înțeles, pentru numere mari ai putea îmbunătăți eficiența verificând doar până la rădăcina pătrată, ca în exemplul anterior!

Structura corectă a programelor C++

Iată cum arată un program corect formatat în IDE (mediul de dezvoltare):

#include <iostream>
using namespace std;

int main() {
    int a, nr;
    bool exist = false;
    cin >> a;
    
    while (a != 0) {
        //verificăm dacă a este prim
        nr = 0;
        for (int d = 1; d <= a; d++)
            if (a % d == 0)
                nr++;
        
        if (nr == 2) {
            exist = true;
            cout << a << " ";
        }
        
        cin >> a;
    }
    
    if (exist == false)
        cout << "Nu există numere prime în șir";
    
    return 0;
}

Când rulezi programul cu input-ul 23 13 3 2, acesta va afișa toate numerele prime din șir: 23 13 3 2.

💡 Important pentru BAC: Asigură-te că programele tale respectă exact această structură și sintaxă! Verifică mereu indentarea și parantezele pentru a evita erori!