Algoritmi elementari (sume, produse, prelucrari cifre, divizori, siruri)

Aceasta lectie acopera algoritmii fundamentali de prelucrare a numerelor naturale si a sirurilor de caractere, esentiali pentru pregatirea examenului de Bacalaureat la Informatica (atât profil real, cât și uman). Vom începe cu algoritmi de sume și produse, care implică parcurgerea unor mulțimi finite (de la 1 la n, sau citite de la tastatură) și acumularea rezultatelor. De exemplu, suma primelor n numere naturale se realizează cu o buclă for și o variabilă s inițializată cu 0.

Produsul numerelor pare dintr-un șir de n numere se construiește cu o variabilă p inițializată cu 1, iar pentru fiecare număr par se înmulțește. Atenție la cazul când nu există niciun număr par – produsul rămâne 1, dar de multe ori se cere să afișăm mesaj corespunzător. Prelucrările cifrelor unui număr natural se bazează pe extragerea ultimei cifre prin n%10 și eliminarea ei prin n/10, într-o buclă while.

Astfel putem determina suma cifrelor, oglinditul (inversul), numărul de cifre, sau să verificăm dacă numărul este palindrom (egal cu oglinditul său). De exemplu, pentru 12321, oglinditul este tot 12321, deci palindrom. Algoritmii cu divizori implică testarea divizibilității: pentru a afla divizorii unui număr n, parcurgem i de la 1 la sqrt(n) și verificăm dacă n % i == 0; dacă da, atât i cât și n/i sunt divizori (cu excepția cazului când i = n/i).

Astfel putem determina suma divizorilor, numărul de divizori, sau dacă numărul este prim (are exact 2 divizori). Prelucrarea șirurilor de caractere se face prin parcurgerea caracterelor cu ajutorul funcției length() și accesarea prin index (sir[i]). Operații frecvente: numărarea aparițiilor unui caracter, transformarea literelor mici în mari (prin scăderea lui 32 din codul ASCII), verificarea dacă un șir este palindrom, sau eliminarea spațiilor.

Toți acești algoritmi se implementează în pseudocod sau în limbajul C++ (de obicei, la Bac se cere pseudocod sau C++). Recomand să scrieți întâi algoritmul pe hârtie, să testați cu exemple simple, și apoi să îl transpuneți în cod. În lecția de față vom vedea aplicații concrete, cu rezolvări pas cu pas.

Exemple

• Exemplul 1 (Suma cifrelor unui număr): Se citește un număr natural n. Să se calculeze suma cifrelor sale. Rezolvare: inițializăm s=0; cât timp n>0, extragem ultima cifră c=n%10, adunăm c la s, apoi eliminăm ultima cifră n=n/10. La final, afișăm s. Test: n=123 -> s=0+3=3, n=12; s=3+2=5, n=1; s=5+1=6, n=0 -> afișează 6.
• Exemplul 2 (Verificare număr prim): Se citește un număr natural n. Să se verifice dacă n este prim. Rezolvare: dacă n<2 => nu e prim. Altfel, presupunem prim=1 (adevărat); pentru i de la 2 la sqrt(n), dacă n%i==0, atunci prim=0 și ieșim din buclă. La final, dacă prim=1, n este prim. Test: n=17, sqrt(17)≈4; i=2: 17%2=1, i=3: 17%3=2, i=4: 17%4=1 -> prim rămâne 1, deci 17 este prim.
• Exemplul 3 (Palindrom într-un șir de caractere): Se citește un șir s (fără spații). Să se verifice dacă este palindrom. Rezolvare: inițializăm i=0, j=length(s)-1; cât timp i<j, dacă s[i]!=s[j], atunci nu e palindrom și ne oprim; altfel, i++, j--. Dacă bucla se termină, șirul este palindrom. Test: s='capac' -> i=0, j=4, s[0]='c', s[4]='c' egal; i=1, j=3, s[1]='a', s[3]='a' egal; i=2, j=2 -> se oprește; este palindrom.

Concepte cheie: Inițializarea corectă a variabilelor de acumulare (suma cu 0, produsul cu 1), Extragerea și eliminarea cifrelor unui număr natural (n%10, n/10), Parcurgerea eficientă a divizorilor până la radical din n, Testarea apartenenței unui șir la clasa palindromurilor, Transpunerea algoritmilor în pseudocod și C++ pentru Bacalaureat