Programare Competitivă

Funcții care returnează valori

Am văzut deja funcții cu return. În această lecție aprofundăm: cum proiectăm funcții care calculează și întorc un rezultat, și cum le folosim eficient.

Funcții de calcul

Cel mai simplu tip: primesc date, calculează, returnează.

int factorial(int n) {
    int p = 1;
    for (int i = 1; i <= n; i++)
        p = p * i;
    return p;
}

Apel:

cout << factorial(5);       // 120
int x = factorial(3) + 1;  // 7

Rezultatul funcției poate fi folosit direct în expresii, afișări sau atribuit unei variabile.

Funcții de verificare (bool)

Returnează true sau false. Sunt extrem de utile pentru a face codul lizibil.

Verificare număr prim

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

Verificare palindrom (număr)

bool estePalindrom(int n) {
    int copie = n, og = 0;
    while (copie > 0) {
        og = og * 10 + copie % 10;
        copie = copie / 10;
    }
    return n == og;
}

Verificare număr perfect

Un număr perfect este egal cu suma divizorilor săi (fără el însuși): 6 = 1 + 2 + 3.

bool estePerfect(int n) {
    int suma = 0;
    for (int d = 1; d < n; d++)
        if (n % d == 0)
            suma = suma + d;
    return suma == n;
}

Folosire

int main()
{
    for (int i = 1; i <= 100; i++) {
        if (estePrim(i) && estePalindrom(i))
            cout << i << " ";
    }
    return 0;
}

Codul din main se citește aproape ca în limba română: “dacă este prim și este palindrom, afișează”.

Funcții de calcul cu numere

CMMDC

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

CMMMC (folosind CMMDC)

int cmmmc(int a, int b) {
    return a / cmmdc(a, b) * b;
}

O funcție poate apela altă funcție. cmmmc apelează cmmdc - cod curat și reutilizabil.

Ridicare la putere

long long putere(int baza, int exp) {
    long long rez = 1;
    for (int i = 1; i <= exp; i++)
        rez = rez * baza;
    return rez;
}

Funcții pe vectori

Funcțiile pot lucra pe vectori. Vectorul se transmite ca parametru împreună cu dimensiunea n.

Suma elementelor

int suma(int v[], int n) {
    int s = 0;
    for (int i = 1; i <= n; i++)
        s = s + v[i];
    return s;
}

Maximul

int maxim(int v[], int n) {
    int mx = v[1];
    for (int i = 2; i <= n; i++)
        if (v[i] > mx)
            mx = v[i];
    return mx;
}

Numărare cu condiție

int nrPrime(int v[], int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (estePrim(v[i]))
            cnt++;
    return cnt;
}

Folosire

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001], n;

// ... funcțiile de mai sus ...

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    fout << "Suma: " << suma(v, n) << endl;
    fout << "Maxim: " << maxim(v, n) << endl;
    fout << "Numere prime: " << nrPrime(v, n) << endl;

    return 0;
}

Funcții void care modifică vectori

Când funcția trebuie să modifice vectorul (sortare, inversare), folosim void:

Inversarea unui vector

void inverseaza(int v[], int n) {
    int st = 1, dr = n;
    while (st < dr) {
        int aux = v[st];
        v[st] = v[dr];
        v[dr] = aux;
        st++;
        dr--;
    }
}

Sortare

void sorteaza(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int pozMin = i;
        for (int j = i + 1; j <= n; j++)
            if (v[j] < v[pozMin])
                pozMin = j;
        int aux = v[i];
        v[i] = v[pozMin];
        v[pozMin] = aux;
    }
}

return oprește funcția

return nu doar trimite o valoare - oprește imediat execuția funcției.

bool contine(int v[], int n, int x) {
    for (int i = 1; i <= n; i++)
        if (v[i] == x)
            return true;   // găsit - ieșim imediat
    return false;           // am parcurs tot, nu l-am găsit
}

Când se găsește x, funcția se oprește fără a mai parcurge restul vectorului.

Exemplu complet: program cu mai multe funcții

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001], n;

void citeste(int v[], int &n) {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
}

void afiseaza(int v[], int n) {
    for (int i = 1; i <= n; i++)
        fout << v[i] << " ";
    fout << endl;
}

void sorteaza(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int pozMin = i;
        for (int j = i + 1; j <= n; j++)
            if (v[j] < v[pozMin])
                pozMin = j;
        int aux = v[i];
        v[i] = v[pozMin];
        v[pozMin] = aux;
    }
}

int maxim(int v[], int n) {
    int mx = v[1];
    for (int i = 2; i <= n; i++)
        if (v[i] > mx) mx = v[i];
    return mx;
}

int main()
{
    citeste(v, n);
    fout << "Maxim: " << maxim(v, n) << endl;
    sorteaza(v, n);
    fout << "Sortat: ";
    afiseaza(v, n);

    return 0;
}

main este acum doar 5 linii - clar, concis, ușor de înțeles.

Greșeli frecvente

1. Funcția nu returnează pe toate ramurile

int maxim(int a, int b) {
    if (a > b) return a;
    // dacă a <= b, nu returnează nimic - EROARE!
}

Trebuie return b; pe ramura else.

2. Folosirea rezultatului unei funcții void

void afiseaza(int x) { cout << x; }

int a = afiseaza(5); // GREȘIT - void nu returnează nimic

3. Vectorul transmis fără dimensiune

int suma(int v[]) {         // De unde până unde parcurgem?
    for (int i = 1; i <= ???; i++)

Mereu transmitem și n (dimensiunea):

int suma(int v[], int n) {  // CORECT

Ce să reții

  • Funcțiile cu return calculează și întorc o valoare.
  • Funcțiile bool sunt ideale pentru verificări (estePrim, estePar).
  • O funcție poate apela altă funcție (cmmmc apelează cmmdc).
  • return oprește imediat funcția.
  • Vectorii se transmit cu dimensiunea n.
  • Cu funcții bine scrise, main devine scurt și clar.
Cuprins Inapoi Inainte