Reprezentarea numerelor mari — un vector de cifre

De ce nu încap în long long

În C++, tipurile native au o margine fixă, dată de numărul de biți:

• int are 32 de biți → ține numere până la circa 2 × 10⁹ (10 cifre);
• long long are 64 de biți → ține până la circa 9,2 × 10¹⁸, adică maximum 19 cifre.

Asta e suficient pentru multe probleme, dar nu pentru toate. La concurs apar des cerințe gen „calculează 100!” (factorialul lui 100, care are 158 de cifre) sau „al 200-lea număr Fibonacci”. Astfel de valori depășesc cu mult orice tip nativ.

Ce se întâmplă când depășești? Nu primești eroare — primești un rezultat fals. Valoarea „se învârte” (overflow): aduni două numere mari pozitive și obții brusc un număr negativ sau o cifră aiurea. Programul rulează liniștit și îți dă un răspuns greșit, ceea ce e și mai periculos decât o eroare vizibilă.

Concluzia: dacă numărul poate depăși 18–19 cifre, nu îl mai poți ține într-o singură variabilă. Avem nevoie de o altă reprezentare.

Reprezentarea: un vector de cifre, inversat

Ideea fundamentală a întregului capitol: stocăm un număr mare ca un vector<int> în care fiecare element este o singură cifră zecimală (bază 10, pentru claritate didactică). Convenția pe care o fixăm aici și o vom folosi identic în toate lecțiile:

Cifra unităților stă pe indexul 0. Adică ținem cifrele inversat (little-endian): cifre[0] = unitățile, cifre[1] = zecile, cifre[2] = sutele.

De ce inversat, nu în ordinea „normală”? Pentru că la adunare, scădere și înmulțire transportul („carry-ul”) pleacă mereu de la unități și curge spre cifrele tot mai mari. Dacă unitățile sunt pe indexul 0, transportul curge dinspre index mic spre index mare — adică în direcția firească de parcurgere a vectorului. Astfel buclele viitoare devin curate și fără surprize. Dacă am ține cifrele în ordinea normală, ar trebui să parcurgem mereu de la coadă spre cap, complicând inutil codul.

Exemplu pas cu pas

Luăm numărul 4071 și îl punem în vector după convenția noastră:

• cifra unităților este 1 → cifre[0] = 1
• cifra zecilor este 7 → cifre[1] = 7
• cifra sutelor este 0 → cifre[2] = 0
• cifra miilor este 4 → cifre[3] = 4

Deci cifre = [1, 7, 0, 4]. Vectorul „arată” inversat față de cum scriem numărul, dar asta e exact ce vrem. Ca să afișăm numărul înapoi, parcurgem de la indexul cel mai mare spre 0: 4, 0, 7, 1 → „4071”. Numărul de cifre este cifre.size().

Implementare C++

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

int main() {
    string s = "4071";          // citim numarul ca text
    vector<int> cifre;          // aici stocam cifrele, inversat

    // parcurgem string-ul de la coada spre cap:
    // ultimul caracter al string-ului = cifra unitatilor = index 0
    for (int i = s.size() - 1; i >= 0; i--) {
        cifre.push_back(s[i] - '0');   // '7' - '0' = 7 (din char in int)
    }
    // acum cifre = [1, 7, 0, 4]

    // afisare: de la indexul cel mai mare spre 0
    for (int i = cifre.size() - 1; i >= 0; i--) {
        cout << cifre[i];       // 4, apoi 0, apoi 7, apoi 1
    }
    cout << "\n";               // afiseaza: 4071

    cout << cifre.size() << "\n";   // 4 (numarul are 4 cifre)
    return 0;
}

Recapitulare

• Tipurile native au limită fixă: long long ține maximum ~19 cifre, apoi dă overflow tăcut.
• Stocăm un număr mare ca vector<int> cu o cifră per element, inversat: unitățile pe indexul 0.
• Citim numărul ca string și îl punem în vector de la coadă spre cap; afișăm de la size() - 1 spre 0.