Reprezentarea numerelor mari — cifră cu cifră

De ce contează?

Un calculator de buzunar se blochează la numere prea mari, dar tu poți aduna pe hârtie numere de o sută de cifre, cifră cu cifră, cu transport. Exact asta facem în program: dacă numărul nu încape într-un tip standard, îl ținem ca pe o listă de cifre și lucrăm ca pe hârtie.

De ce numere mari

Tipurile standard au limite: int ajunge până la ~2·10⁹, long long până la ~9·10¹⁸. Dar 100! are 158 de cifre, iar multe probleme cer numere cu sute de cifre. Acolo niciun tip nu ajunge — trebuie să ne construim propriul „număr".

Observația-cheie

Ideea de bază: un număr mare e doar un șir de cifre. Îl stocăm într-un vector și implementăm operațiile (adunare, scădere, înmulțire) imitând algoritmii de pe hârtie.

Stocarea: vector de cifre, unitățile primele

Reprezentăm numărul ca un vector în care fiecare element e o cifră, în ordine inversă: unitățile pe poziția 0, zecile pe 1, etc.

Numărul 4072 devine:

2	7	0	4
0	1	2	3

4072 stocat invers: v[0]=2 (unități), v[1]=7 (zeci), v[2]=0 (sute), v[3]=4 (mii).

De ce invers? Operațiile aritmetice pornesc de la unități și „transportă" spre stânga. Cu unitățile pe indexul 0, transportul crește indicele natural — fără socoteli de poziție inversă. În plus, când numărul crește (o cifră în plus), doar adaugi la coada vectorului.

Citirea dintr-un șir de caractere

Numărul mare se citește de obicei ca string (poate avea sute de cifre), apoi îl convertim în vector de cifre inversat:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> citeste() {
    string s;
    cin >> s;
    vector<int> nr;
    // parcurg de la dreapta (unitati) la stanga
    for (int i = s.size() - 1; i >= 0; i--) {
        nr.push_back(s[i] - '0');   // caracter cifra -> valoare
    }
    return nr;
}

s[i] - '0' transformă caracterul '7' în valoarea 7.

Afișarea

Afișezi în ordine inversă față de stocare — de la cea mai semnificativă cifră (ultimul index) la unități:

void afiseaza(const vector<int> &nr) {
    for (int i = nr.size() - 1; i >= 0; i--) {
        cout << nr[i];
    }
    cout << "\n";
}

Eliminarea zerourilor din față

După operații (mai ales scădere), pot rămâne zerouri nesemnificative la coada vectorului (adică în fața numărului). Le elimini, dar lași măcar o cifră pentru numărul 0:

void normalizeaza(vector<int> &nr) {
    while (nr.size() > 1 && nr.back() == 0) {
        nr.pop_back();   // scot zero nesemnificativ din fata numarului
    }
}

Observația-cheie

Vectorul de cifre poate folosi și „cifre" mai mari decât baza 10 (de exemplu grupuri de 9 cifre în baza 10⁹) pentru viteză. La început rămânem însă la baza 10 — o cifră zecimală pe poziție — fiindcă e cel mai ușor de înțeles.

Greșeli frecvente

Capcane la reprezentarea numerelor mari:

Citești numărul ca int/long long: depășește tipul înainte să apuci să-l procesezi. Citește-l ca string.
Confuzi ordinea de stocare cu cea de afișare: stochezi invers (unitățile primele), dar afișezi de la cea mai mare cifră. Inversarea greșită produce numărul oglindit.
Uiți s[i] - '0': dacă pui caracterul direct, lucrezi cu codul ASCII ('7' = 55), nu cu valoarea 7.
Lași zerouri în față: după scădere rămân zerouri nesemnificative la coada vectorului; normalizează, dar păstrează o cifră pentru numărul 0.

Recapitulare

Numerele care depășesc long long se reprezintă ca vector de cifre.
Stochezi cifrele invers (unitățile pe indexul 0), ca transportul să crească indicele natural; afișezi în ordine inversă.
Citești numărul ca string, converteșți cu s[i] - '0' și normalizează zerourile nesemnificative din față.