Probleme simple de algoritmică rezolvate

Teoria e utilă, dar algoritmica se învață rezolvând. În acest articol luăm patru probleme clasice, exact genul care apare la concursuri și la Bac, și le descompunem pas cu pas. Pentru fiecare, gândim întâi logica, apoi scriem codul.

1. Este un număr prim?

Un număr e prim dacă are exact doi divizori: 1 și el însuși. Cum verificăm? Încercăm să-l împărțim la fiecare număr de la 2 până la rădăcina lui. Dacă vreunul îl împarte exact, nu e prim.

#include <iostream>

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

int main() {
    int n;
    std::cin >> n;
    if (estePrim(n))
        std::cout << n << " este prim." << std::endl;
    else
        std::cout << n << " nu este prim." << std::endl;
    return 0;
}

De ce d * d <= n și nu d <= n? Dacă n are un divizor mai mare decât rădăcina lui, atunci are obligatoriu și unul mai mic. Verificăm doar până la rădăcină și câștigăm enorm în viteză.

2. Este un cuvânt palindrom?

Un palindrom se citește la fel de la stânga la dreapta și invers ("cojoc", "rotor"). Comparăm primul caracter cu ultimul, al doilea cu penultimul, și tot așa spre mijloc.

#include <iostream>
#include <string>

int main() {
    std::string s;
    std::cin >> s;

    int st = 0, dr = s.size() - 1;
    bool palindrom = true;

    while (st < dr) {
        if (s[st] != s[dr]) {
            palindrom = false;
            break;
        }
        st++;
        dr--;
    }

    std::cout << (palindrom ? "Este palindrom" : "Nu este palindrom") << std::endl;
    return 0;
}

Tehnica celor doi indici (unul de la stânga, unul de la dreapta, care se apropie) e un tipar pe care îl vei reîntâlni des în algoritmică.

3. Maximul și poziția lui într-un șir

Citim n numere și aflăm care e cel mai mare și pe ce poziție se află.

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);

    for (int i = 0; i < n; i++) std::cin >> v[i];

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

    std::cout << "Maxim: " << maxim
              << " pe pozitia " << pozitie << std::endl;
    return 0;
}

Ideea de aur: presupunem că primul element e maximul, apoi parcurgem restul și actualizăm de câte ori găsim ceva mai mare. Acest tipar "presupune și actualizează" rezolvă o grămadă de probleme.

4. Șirul lui Fibonacci

Fiecare termen e suma celor doi dinaintea lui: 0, 1, 1, 2, 3, 5, 8, 13... Afișăm primii n termeni fără să consumăm memorie inutilă — ținem doar ultimele două valori.

#include <iostream>

int main() {
    int n;
    std::cin >> n;

    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        std::cout << a << " ";
        long long urmator = a + b;
        a = b;
        b = urmator;
    }
    std::cout << std::endl;
    return 0;
}

Am folosit long long pentru că numerele Fibonacci cresc foarte repede și depășesc capacitatea unui int obișnuit. E un detaliu care te scapă de multe surprize la concursuri.

Cum abordezi orice problemă nouă

Pas	Întrebare pe care ți-o pui
1. Înțelege	Ce intrare am? Ce ieșire vreau?
2. Exemplu	Rezolv pe hârtie pentru un caz mic
3. Tipar	Seamănă cu ceva ce știu deja?
4. Cod	Scriu și testez pe exemplul de la pasul 2
5. Cazuri limită	Ce se întâmplă la 0, la negative, la șir gol?

Cel mai important sfat: înainte să scrii o linie de cod, rezolvă problema pe hârtie pentru un exemplu mic. Dacă nu o poți rezolva manual, nu o poți programa.

Continuă să exersezi

Aceste patru probleme conțin tipare pe care le vei folosi în sute de altele: căutarea unui divizor, doi indici, "presupune și actualizează", recurența. Stăpânește-le și ai o fundație solidă.

---

La ByteSchool rezolvăm împreună problemă după problemă, exact ca la antrenament. Cu mentori din Big Tech care îți arată cum gândesc ei o soluție, treci de la "nu știu de unde să încep" la "știu ce tipar aplic". Pas cu pas, devii rezolvitorul de probleme care punctează la concursuri și la Bac. Te așteptăm.