Prelucrarea cifrelor

Numerele de cel mult trei cifre

Pentru a introduce conceptul, vom pleca de la cazurile cele mai simple, și anume numerele cu cel mult trei cifre. Ele apar în multe probleme, iar deși metodele pe care le vom explica aici le putem folosi și pentru numere cu mai multe cifre, nu este practic să le folosim deoarece putem folosi structurile repetitive într-un mod mai simplu și eficient.

Dacă vrem să aflăm cifrele unui număr cu cel mult 3 cifre, putem să ne folosim de diverse relații matematice pentru a le afla, începând de la ultima la prima.

Pentru a afla această cifră, ne vom folosi de proprietatea că aceasta este egală cu restul împărțirii numărului la 10, ceea ce ne va da rezultatul dorit.

Pentru a afla următoarele cifre, avem mai multe variante. Fie împărțim numărul la 10 și aflăm de fiecare dată noua cifră a unităților la fel ca la pasul precedent, fie vom folosi o formulă modificată pe care o vom prezenta aici:

Mai jos puteți vedea o secvență de cod în care prezentăm ambele metode, care funcționează pentru numerele de cel mult trei cifre.

#include <iostream>
using namespace std;

int main() {
    int n;  // numar natural cel mult egal cu 999
    cin >> n;

    // cifrele luate una dupa alta, fara impartiri

    int ultima = n % 10;
    int penultima = (n / 10) % 10;
    int antepenultima = (n / 100) % 10;

    cout << antepenultima << " " << penultima << " " << ultima << '\n';

    // cifrele luate una dupa alta, cu impartiri

    ultima = n % 10;
    n = n / 10;
    penultima = n % 10;
    n = n / 10;
    antepenultima = n % 10;
    n = n / 10;

    cout << antepenultima << " " << penultima << " " << ultima << '\n';
    return 0;
}

Numerele de lungime oarecare

Acum că am învățat cum să aflăm cifrele unui număr, vom generaliza modul de aflare a cifrelor unui număr în general.

Deoarece nu putem depinde la nesfârșit de metodele de mai sus din lipsa de practicabilitate ale acestora, trebuie să ne gândim la o metodă ce folosește o structură repetitivă pentru a afla cifrele unui număr $n$.

De obicei, deoarece nu știm câte cifre va avea $n$, vom folosi instrucțiunea while deoarece aceasta ne dă flexibilitatea să ne oprim atunci când numărul nostru nu mai are cifre.

Un cod tipic pentru aflarea cifrelor unui număr de la ultima la prima va arăta așa:

#include <iostream>
using namespace std;

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

    if (n == 0) {
        // caz particular daca n = 0
    }

    while (n > 0) {
        int c = n % 10;
        n = n / 10;
    }
    return 0;
}

De regulă, operațiile ce țin de cifrele găsite se vor efectua în while, indiferent că e vorba de găsirea unor valori auxiliare, numărarea cifrelor care respectă o anumită proprietate sau calcularea unor sume, maxime etc.

Problema Suma cifrelor unui număr

View Problem

PBInfo

Deschide

Pentru a afla suma cifrelor unui număr, vom folosi algoritmul prezentat anterior și vom aduna la răspuns valoarea cifrei curente.

#include <iostream>
using namespace std;

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

    int s = 0;
    while (n > 0) {
        s = s + n % 10;
        n = n / 10;
    }

    cout << s;
    return 0;
}

Problema Control

View Problem

PBInfo

Deschide

Cifra de control este un concept ce se regăsește frecvent în problemele de algoritmică românești, mai ales la problemele din examene sau problemele mai ușoare de olimpiadă.

Criteriul de divizibilitate cu 9 (învățat la matematică în clasa a 5-a) spune că $x$ și suma cifrelor lui $x$ dau același rest la împărțirea cu 9. În particular, se poate observa faptul că cifra de control este fix rezultatul operației $x \% 9$, cu două particularități pe care trebuie să le avem în vedere:

• Dacă $x = 0$, cifra de control a lui $x$ este 0
• Dacă $x\% 9 = 0$, cifra de control a lui $x$ este 9.

Mai jos puteți găsi implementări folosind atât formula simplificată, cât și simularea răspunsului.

#include <iostream>
using namespace std;

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

    // cat timp n > 9, aflam suma cifrelor si modificam n
    while (n > 9) {
        int n2 = n;
        n = 0;
        while (n2) {
            n += n2 % 10;
            n2 /= 10;
        }
    }

    cout << n << '\n';
    return 0;
}

#include <iostream>
using namespace std;

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

    if (n == 0) {
        cout << 0 << '\n';
    } else {
        if (n % 9 == 0) {
            cout << 9 << '\n';
        } else {
            cout << n % 9 << '\n';
        }
    }

    return 0;
}

Problema Oglinditul unui număr

View Problem

PBInfo

Deschide

Pentru a afla oglinditul unui număr, vom folosi algoritmul prezentat anterior, împreună cu ținerea unei variabile care să ne țină numărul inversat.

#include <iostream>
using namespace std;

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

    int og = 0;
    while (n > 0) {
        og = og * 10 + n % 10;
        n = n / 10;
    }

    cout << og;
    return 0;
}

Problema Aparitii2

View Problem

PBInfo

Deschide

Pentru a afla de câte ori apare prima cifră a numărului dat, mai întâi va trebui să aflăm care este prima cifră, iar mai apoi, vom parcurge numărul din nou pentru a număra aparițiile primei cifre.

#include <iostream>
using namespace std;

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

    int n2 = n;
    while (n2 >= 10) {
        n2 /= 10;
    }

    int aparitii = 1;  // prima cifra, evitam tratarea separata a cazului n = 0
    while (n >= 10) {
        if (n % 10 == n2) {
            aparitii++;
        }
        n = n / 10;
    }

    cout << aparitii;
    return 0;
}

Probleme suplimentare

• NumarulDeCifre pbinfo
• UltimaCifraPara pbinfo
• ProdusCifreImpare pbinfo
• prod_k pbinfo
• aparitii pbinfo
• OMI Iasi 2020 codjoc
• alternant1 pbinfo
• Alte probleme cu aflarea cifrelor unui număr de pe pbinfo
• Sequence With Digits
• OJI 2019 aur

Resurse suplimentare

• Parcurgerea cifrelor unui număr - CPPI Sync
• Prelucrarea cifrelor unui numar - Algopedia
• Cifrele unui număr - pbinfo