Cifrele unui număr

Pentru un întreg nenegativ, ultima cifră este restul împărțirii la 10, iar eliminarea ei se face prin împărțire întreagă la 10. Astfel, din 742 obținem succesiv cifrele 2, 4, 7, în ordine inversă scrierii numărului. Cazul 0 cere atenție: numărul 0 are o cifră, deși o buclă cu testul n > 0 nu ar executa nicio iterație.

În Python, pentru n=123, expresia n % 10 dă ultima cifră, 3, iar n // 10 lasă 12.

Cifrele unui număr natural scris în baza 10 se extrag de la dreapta la stânga cu două operații: n % 10 dă ultima cifră, iar n / 10 (împărțire întreagă; în Python n // 10) elimină ultima cifră. Pentru $n=583$ avem $583\mathrm{mod}10=3$ și $[583/10]=58$. Dacă repeți cele două operații până când numărul devine 0, obții toate cifrele, în ordinea inversă scrierii. Un număr cu $k$ cifre cere $k$ repetări, deci timpul este proporțional cu $k$, adică cu $[\lg n]+1$ pentru $n\ge 1$, iar memoria auxiliară este constantă.

Alegerea ciclului contează pentru $n=0$. Ciclul while (n > 0) nu execută niciun pas, deci ar număra zero cifre, deși 0 se scrie cu o cifră. Ciclul do ... while (n > 0) execută corpul o dată și tratează corect cazul. Pentru un număr negativ se lucrează cu modulul, iar enunțul precizează dacă semnul contează.

Exemplul 1 — suma și numărul cifrelor. Pentru $n=583$ stările sunt:

1. cifra 3, suma 3, numărul de cifre 1, iar $n$ devine 58;
2. cifra 8, suma 11, numărul de cifre 2, iar $n$ devine 5;
3. cifra 5, suma 16, numărul de cifre 3, iar $n$ devine 0 și ciclul se oprește.

#include <iostream>
using namespace std;
int main() {
    int n = 583, suma = 0, nr = 0;
    do {
        suma += n % 10;
        nr++;
        n /= 10;
    } while (n > 0);
    cout << suma << ' ' << nr;
    return 0;
}

Programul afișează 16 3. Pentru $n=0$ inițial, corpul se execută o dată și rezultatul este 0 1.

Exemplul 2 — inversul unui număr (Python). Cifrele extrase se alipesc într-un număr nou cu formula $\text{invers}\leftarrow \text{invers}\cdot 10+\text{cifra}$, deci prima cifră extrasă ajunge la cea mai mare putere a lui 10.

n = int(input())
invers = 0
while True:
    cifra = n % 10
    invers = invers * 10 + cifra
    n //= 10
    if n == 0:
        break
print(invers)

Pentru intrarea 583, perechile (cifra, invers) sunt $(3;3)$, $(8;38)$, $(5;385)$, deci se afișează 385. Pentru intrarea 1200 se afișează 21: zerourile de la sfârșitul lui 1200 devin zerouri de la începutul inversului și dispar din valoarea numerică.

Exemplul 3 — filtrarea cifrelor. Pentru a păstra într-un număr nou doar cifrele impare, în aceeași ordine ca în numărul inițial, folosești un multiplicator p care crește de zece ori la fiecare cifră păstrată: nou += cifra * p; p *= 10;. Pentru 4721 cifrele impare sunt 7 și 1; se extrag în ordinea 1, 7, deci nou devine $1\cdot 1+7\cdot 10=71$.

Aceeași extragere răspunde la întrebări de numărare și de optim. Pentru a număra aparițiile unei cifre $c$ crești un contor ori de câte ori n % 10 == c; în 4721 cifra 2 apare o dată. Pentru cea mai mare cifră compari fiecare cifră extrasă cu maximul de până atunci și obții 7 pentru același număr. Ambele variante parcurg numărul o singură dată.

Exemplul 4 — palindromul și depășirea. Un număr este palindrom dacă este egal cu inversul său. Fiindcă extragerea distruge pe n, valoarea inițială se copiază întâi într-o variabilă copie.

#include <iostream>
using namespace std;
int main() {
    long long n = 1221, copie = n, invers = 0;
    while (n > 0) {
        invers = invers * 10 + n % 10;
        n /= 10;
    }
    cout << (invers == copie ? "da" : "nu");
    return 0;
}

Pentru 1221 valorile lui invers sunt 1, 12, 122, 1221, egal cu copie, deci se afișează da. Pentru 1231 se obține 1321, diferit de 1231, deci nu. Tipul long long nu este întâmplător: pentru $n=2000000003$ inversul ar fi $3000000002$, mai mare decât cea mai mare valoare int, $2147483647$, iar rezultatul ar fi greșit.

La problemele cu cifre, distinge ordinea de extragere (de la dreapta la stânga) de ordinea în care se formează rezultatul. Formula rez = rez * 10 + cifra inversează ordinea cifrelor extrase, pe când rez += cifra * p, cu p înmulțit cu 10 la fiecare cifră păstrată, o păstrează. Urmărește în tabel valorile lui n, cifra și rez după fiecare iterație și nu uita testul de oprire: bucla se termină când $n$ devine 0, nu când cifra extrasă este 0. Un număr cu $k$ cifre produce exact $k$ iterații, deci 4702 produce patru.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int n = 4702, x = 0;
while (n > 0) {
    int c = n % 10;
    if (c % 2 == 0)
        x = x * 10 + c;
    n /= 10;
}
cout << x;

• a) 402
• b) 204
• c) 4702
• d) 2040

Răspunsul corect este b). Cifrele se extrag în ordinea 2, 0, 7, 4. Cifra 2 este pară: $x=0\cdot 10+2=2$. Cifra 0 este pară: $x=2\cdot 10+0=20$. Cifra 7 este impară și $x$ rămâne 20. Cifra 4 este pară: $x=20\cdot 10+4=204$. Varianta a) păstrează ordinea din scrierea lui 4702, adică 4, 0, 2, dar secvența inversează ordinea. Varianta d) ar apărea dacă la final s-ar mai înmulți $x$ cu 10.

Al doilea exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int n = 35281, k = 0;
while (n > 0) {
    if (n % 10 > 3)
        k++;
    n /= 10;
}
cout << k;

• a) 2
• b) 3
• c) 5
• d) 4

Răspunsul corect este a). Cifrele se extrag în ordinea 1, 8, 2, 5, 3 și $n$ devine pe rând 3528, 352, 35, 3, 0. Condiția > 3 este adevărată doar pentru 8 și 5, deci $k=2$. Varianta b) ar rezulta din condiția >= 3, care ar număra și cifra 3. Varianta c) ar număra toate cifrele, ca și cum condiția ar fi mereu adevărată.

Greșeli frecvente

• Greșit: n % 10 dă prima cifră din stânga.
  Corect: dă ultima cifră.
• Greșit: zero are zero cifre.
  Corect: reprezentarea lui 0 are o cifră.
• Greșit: inversul numeric al lui 120 este un întreg cu trei cifre, 021.
  Corect: ca număr întreg este 21.

Înainte și după