Sari la conținut
EduCamp

Tematică științifică · 1.5

Algoritmi elementari

Prelucrarea cifrelor unui număr, divizibilitatea și divizorii, testarea primalității, algoritmul lui Euclid, descompunerea în factori primi, prelucrarea secvențelor de valori și generarea șirurilor recurente, scrise în pseudocod, în C++ și în Python.

Algoritmii elementari sunt cei pe care se bazează rezolvarea problemelor:

  • probleme cu numere și cu cifrele numerelor;
  • probleme de divizibilitate;
  • prelucrarea unor secvențe de valori;
  • generarea șirurilor recurente.

Aceștia se cer la examen scriși ca subprogram, cu antetul dat în enunț: subprogramul primește un număr sau o secvență și întoarce un rezultat, iar restul rezolvării îl apelează. De aceea algoritmii de mai jos sunt scriși în aceeași formă, în pseudocod și în cele două limbaje.

Prelucrarea cifrelor unui număr

Toate prelucrările cifrelor se sprijină pe două operații. Restul împărțirii la 10 este ultima cifră a numărului, cea mai puțin semnificativă. Câtul împărțirii întregi la 10 este numărul rămas după eliminarea acestei cifre.

cât timp n ≠ 0 execută
    c ← n % 10          { se extrage cifra curentă, de la dreapta spre stânga }
    { se prelucrează cifra c }
    n ← [n / 10]        { se elimină cifra prelucrată }
sfcât timp

Structura rămâne aceeași de la o problemă la alta; se schimbă numai prelucrarea cifrei.

ProblemaPrelucrarea cifrei
suma cifrelors ← s + c
produsul cifrelorp ← p * c
numărul de cifrenr ← nr + 1
cifra maximădacă c > maxim atunci maxim ← c
numărul cifrelor paredacă c % 2 = 0 atunci nr ← nr + 1
răsturnatul număruluirasturnat ← rasturnat * 10 + c

Suma cifrelor este cel mai cerut subprogram al acestui subcapitol.

Algoritm

sumaCifrelor(n):
    s ← 0
    cât timp n ≠ 0 execută
        s ← s + n % 10
        n ← [n / 10]
    sfcât timp
    returnează s

C++

int sumaCifrelor(int n) {
    int s = 0;
    while (n != 0) {
        s = s + n % 10;
        n = n / 10;
    }
    return s;
}

Python

def suma_cifrelor(n):
    s = 0
    while n != 0:
        s = s + n % 10
        n = n // 10
    return s

Răsturnatul unui număr se obține prin compunerea numărului din cifrele extrase, în ordine inversă. Un număr este palindrom dacă este egal cu răsturnatul său.

Algoritm

rasturnat(n):
    r ← 0
    cât timp n ≠ 0 execută
        r ← r * 10 + n % 10
        n ← [n / 10]
    sfcât timp
    returnează r

C++

int rasturnat(int n) {
    int r = 0;
    while (n != 0) {
        r = r * 10 + n % 10;
        n = n / 10;
    }
    return r;
}

Python

def rasturnat(n):
    r = 0
    while n != 0:
        r = r * 10 + n % 10
        n = n // 10
    return r

Cifra de control a unui număr se obține adunând cifrele, apoi adunând cifrele sumei obținute și așa mai departe, până când rezultatul are o singură cifră. Pentru 8997899 se obține pe rând 59, apoi 14, apoi 5.

Algoritm

cifraDeControl(n):
    cât timp n > 9 execută
        n ← sumaCifrelor(n)
    sfcât timp
    returnează n

C++

int cifraDeControl(int n) {
    while (n > 9)
        n = sumaCifrelor(n);
    return n;
}

Python

def cifra_de_control(n):
    while n > 9:
        n = suma_cifrelor(n)
    return n

Cifrele distincte nu se pot verifica cu răsturnatul. Se folosește un vector de frecvență cu zece poziții, în care se numără aparițiile fiecărei cifre.

Algoritm

cifreDistincte(n):
    f ← vector de 10 zerouri
    cât timp n ≠ 0 execută
        c ← n % 10
        f[c] ← f[c] + 1
        dacă f[c] > 1 atunci
            returnează fals
        sfdacă
        n ← [n / 10]
    sfcât timp
    returnează adevărat

C++

bool cifreDistincte(int n) {
    int frecventa[10] = {0};
    while (n != 0) {
        int c = n % 10;
        frecventa[c]++;
        if (frecventa[c] > 1)
            return false;
        n = n / 10;
    }
    return true;
}

Python

def cifre_distincte(n):
    frecventa = [0] * 10
    while n != 0:
        c = n % 10
        frecventa[c] += 1
        if frecventa[c] > 1:
            return False
        n = n // 10
    return True

Divizibilitate și divizori

Numărul d este divizor al numărului n dacă restul împărțirii lui n la d este 0, adică n % d = 0.

Generarea divizorilor

Varianta directă încearcă pe rând toate valorile de la 1 la n și efectuează n împărțiri.

Divizorii apar însă în perechi: dacă d este divizor al lui n, atunci și n / d este divizor al lui n. Pentru n = 12 perechile sunt (1, 12), (2, 6) și (3, 4). Din fiecare pereche, cel puțin unul dintre divizori este mai mic sau egal cu rădăcina pătrată a lui n. Se încearcă atunci numai valorile cu d * d ≤ n, iar pentru fiecare divizor găsit se ia în seamă și perechea lui.

Algoritm

divizori(n):
    d ← 1
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            scrie d
            dacă d ≠ [n / d] atunci
                scrie [n / d]
            sfdacă
        sfdacă
        d ← d + 1
    sfcât timp

C++

void divizori(int n) {
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            cout << d << " ";
            if (d != n / d)
                cout << n / d << " ";
        }
}

Python

def divizori(n):
    d = 1
    while d * d <= n:
        if n % d == 0:
            print(d, end=" ")
            if d != n // d:
                print(n // d, end=" ")
        d += 1

Condiția d ≠ n / d împiedică luarea în seamă de două ori a divizorului din mijloc, la numerele care sunt pătrate perfecte: pentru n = 36, divizorul 6 formează pereche cu el însuși.

Aceeași parcurgere dă numărul divizorilor și suma divizorilor; se schimbă numai ce se face cu divizorul găsit.

Algoritm

numarulDivizorilor(n):
    nr ← 0
    d ← 1
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            nr ← nr + 1
            dacă d ≠ [n / d] atunci
                nr ← nr + 1
            sfdacă
        sfdacă
        d ← d + 1
    sfcât timp
    returnează nr

C++

int numarulDivizorilor(int n) {
    int nr = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            nr++;
            if (d != n / d) nr++;
        }
    return nr;
}

Python

def numarul_divizorilor(n):
    nr = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            nr += 1
            if d != n // d:
                nr += 1
        d += 1
    return nr

Divizorii proprii ai lui n sunt divizorii cuprinși între 2 și partea întreagă a lui n/2, adică toți divizorii în afară de 1 și de n însuși.

Testarea primalității

Un număr natural n mai mare decât 1 este prim dacă nu are divizori cuprinși între 2 și partea întreagă a rădăcinii pătrate din n. Marginea se justifică la fel ca la generarea divizorilor: un divizor mai mare decât rădăcina pătrată are întotdeauna perechea lui mai mică decât ea, deci ar fi fost deja găsită.

Algoritm

prim(n):
    dacă n < 2 atunci
        returnează fals
    sfdacă
    dacă n % 2 = 0 atunci
        returnează n = 2
    sfdacă
    d ← 3
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            returnează fals
        sfdacă
        d ← d + 2
    sfcât timp
    returnează adevărat

C++

bool prim(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int d = 3; d * d <= n; d = d + 2)
        if (n % d == 0) return false;
    return true;
}

Python

def prim(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Materialul acesta se citește pe educamp.ro și nu se tipărește.

Ce cuprinde subcapitolul

  1. Prelucrarea cifrelor unui număr
  2. Divizibilitate și divizori
  3. Prelucrarea unei secvențe de valori
  4. Generarea șirurilor recurente
  5. Apariții la examen

Continuă lectura ca și cursant

Cel puțin un subcapitol din fiecare capitol este disponibil gratuit și integral. Pentru a citi toate celelalte subcapitole ale disciplinei, te înscrii la cursul de pregătire.

Cursul cuprinde suportul de curs publicat până acum, care se completează capitol cu capitol, și două întâlniri de câte două ore în fiecare lună. Prima săptămână este gratuită, fără plată și fără card. Dacă vrei să vezi mai întâi cum este prezentată materia, poți reveni la primul subcapitol al capitolului.

Începe săptămâna gratuită Sunt cursant — login

Află când publicăm materiale noi

Materia este publicată treptat, capitol cu capitol. Înscrie-te pentru a primi un e-mail atunci când apare un capitol nou de informatică.

Vei primi mesaje numai despre materia selectată și despre cursul de pregătire. Te poți dezabona oricând, dintr-o singură apăsare.

Surse

  • Ministerul Educației, subiecte și bareme pentru examenul național de definitivare în învățământ, disciplina Informatică, 2012–2025
  • Miloșescu, M., „Informatică. Manual pentru clasa a IX-a, profilul real, intensiv”, Editura Didactică și Pedagogică, București, 2005
  • „Tutorialul de Python”, documentația oficială a limbajului Python, https://docs.python.org/ro/3/tutorial/index.html
Actualizat: 30 august 2026