Numere mari: adunarea

Adunarea a două numere mari se face cifrică, exact ca la școala primară: aduni cifrele poziție cu poziție, propagând transportul (carry) când suma depășește 9.

Lecția presupune că ai citit introducerea - știi deja cum se reprezintă un număr mare ca vector de cifre (LSB la a[1], lungime la a[0]).

Adunarea unui număr mare cu un număr mic

Uneori nu aduni două numere mari, ci un număr mare (vector de cifre) cu un număr mic (care încape în int sau long long). E un caz mai simplu și mai rapid - nu trebuie să transformăm numărul mic într-un vector de cifre.

Ideea

Propagăm numărul mic direct prin cifrele numărului mare, tratându-l ca transport.

Parcurgem cifrele lui a de la stânga (LSB) și:

1. Adăugăm la cifra curentă restul împărțirii transportului la 10.
2. Dacă rezultatul e ≥ 10, scădem 10 și crește transportul cu 1.
3. Reducem transportul prin împărțire la 10.

Continuăm până când transportul devine 0 și am depășit ultima cifră.

Cod

void adunareMic(int a[], int x) {
    int i = 1;
    int transport = x;
    while (i <= a[0] || transport > 0) {
        int suma = a[i] + transport;
        a[i] = suma % 10;
        transport = suma / 10;
        if (i > a[0]) a[0] = i;  // am extins numarul
        i++;
    }
}

Pas cu pas: a = 199, x = 5

a → a[0]=3, a[1]=9, a[2]=9, a[3]=1

Rezultat: a = 204 ✓.

Pentru numere foarte mari adăugate

Dacă x e gigantic (ex. x = 10^12), algoritmul de mai sus funcționează tot, dar trebuie să folosești long long pentru transport:

void adunareMic(int a[], long long x) {
    int i = 1;
    long long transport = x;
    while (i <= a[0] || transport > 0) {
        long long suma = a[i] + transport;
        a[i] = suma % 10;
        transport = suma / 10;
        if (i > a[0]) a[0] = i;
        i++;
    }
}

Complexitate: O(lenA + log x).

Util când faci operații în buclă, de exemplu pentru k = 1..N: suma += k unde suma e număr mare dar k e int.

Algoritm

La fiecare poziție i:

suma = a[i] + b[i] + transport
c[i] = suma % 10        // cifra rezultatului
transport = suma / 10   // propagăm mai departe

Parcurgem poziții de la 1 la max(lenA, lenB). Dacă un număr e mai scurt, cifrele lipsă se consideră 0 (automat, dacă vectorii sunt globali).

La final, dacă mai avem transport > 0, îl scriem ca cifră nouă:

dacă transport > 0 la final:
    c[++len] = transport

Pas cu pas: 457 + 1234 = 1691

Reprezentare:

• a = 457 → a[0]=3, a[1]=7, a[2]=5, a[3]=4
• b = 1234 → b[0]=4, b[1]=4, b[2]=3, b[3]=2, b[4]=1

Adunare cifrică:

Transport final = 0. Rezultat: c[0]=4, c[1]=1, c[2]=9, c[3]=6, c[4]=1 → 1691 ✓.

Pas cu pas: 999 + 1 = 1000 (transport propagat)

• a = 999 → a[0]=3, a[1]=9, a[2]=9, a[3]=9
• b = 1 → b[0]=1, b[1]=1

Transport final = 1 (încă nenul). Adăugăm: c[4] = 1, c[0] = 4.

Rezultat: c = 1000 ✓. Observă că lungimea a crescut cu 1 față de cel mai lung număr de intrare - asta se întâmplă când transportul „deborbează”.

Cod

const int NMAX = 1005;
int a[NMAX], b[NMAX], c[NMAX];

void adunare(int a[], int b[], int c[]) {
    int len = a[0];
    if (b[0] > len) {
        len = b[0];
    }
    int transport = 0;
    for (int i = 1; i <= len; i++) {
        int suma = a[i] + b[i] + transport;
        c[i] = suma % 10;
        transport = suma / 10;
    }
    if (transport > 0) {
        len = len + 1;
        c[len] = transport;
    }
    c[0] = len;
}

Complexitate: O(max(lenA, lenB)).

Exemplu complet: citesc două numere și le adun

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int NMAX = 1005;
int a[NMAX], b[NMAX], c[NMAX];
char s[NMAX];

void citire(int v[]) {
    fin >> s;
    int len = strlen(s);
    v[0] = len;
    for (int i = 1; i <= len; i++) {
        v[i] = s[len - i] - '0';
    }
}

void afisare(int v[]) {
    for (int i = v[0]; i >= 1; i--) {
        fout << v[i];
    }
    fout << "\n";
}

void adunare(int a[], int b[], int c[]) {
    int len = a[0];
    if (b[0] > len) {
        len = b[0];
    }
    int transport = 0;
    for (int i = 1; i <= len; i++) {
        int suma = a[i] + b[i] + transport;
        c[i] = suma % 10;
        transport = suma / 10;
    }
    if (transport > 0) {
        len = len + 1;
        c[len] = transport;
    }
    c[0] = len;
}

int main() {
    citire(a);
    citire(b);
    adunare(a, b, c);
    afisare(c);
    return 0;
}

date.in:

457
1234

date.out:

1691

Aliasing: adunare(a, b, a) e sigură?

Uneori vrei să aduni într-un vector direct (ex. a = a + b). Funcția noastră funcționează corect în acest caz, pentru că la pasul i citim a[i] și b[i] înainte să scriem c[i]. Dacă c = a, scriem peste a[i] doar după ce l-am folosit.

Dar atenție: aliasing-ul lui c cu b funcționează tot pentru același motiv. Totuși, e mai clar să păstrezi c ca vector distinct când e posibil.

Variantă: adunarea mai multor numere

Dacă vrei să aduni N numere mari a₁ + a₂ + ... + aₙ, aplici adunarea iterativ:

int rez[NMAX], temp[NMAX];

int N;
fin >> N;
citire(rez); // primul număr
for (int k = 2; k <= N; k++) {
    citire(temp);
    adunare(rez, temp, rez); // rez = rez + temp
}
afisare(rez);

Aplicație tipică: calcularea sumei primelor N factoriale 1! + 2! + ... + N!, sumei primelor N Fibonacci, etc.

Aplicație: suma primelor N numere

Calculează 1 + 2 + 3 + ... + N pentru N ≤ 10⁴ (suma are ~8 cifre, încape în long long, dar hai să facem cu numere mari ca exercițiu).

int suma[NMAX], unu[NMAX], curent[NMAX];

// suma = 0 (automat 0, nu trebuie setat)
suma[0] = 1; // lungime 1, cifra 0

// curent = 0 la început, apoi incrementăm
curent[0] = 1;
curent[1] = 0;

// unu = 1
unu[0] = 1;
unu[1] = 1;

int N;
fin >> N;
for (int k = 1; k <= N; k++) {
    adunare(curent, unu, curent); // curent++
    adunare(suma, curent, suma);   // suma += curent
}
afisare(suma);

Pentru N = 10: răspuns 55. Pentru N = 1000: răspuns 500500. Pentru N = 10⁴: răspuns 50005000. (Toate încap în long long, dar dacă N = 10⁹, suma depășește long long - aici ar fi util numerele mari.)

Un exemplu care clar depășește long long: suma a 10¹⁰ numere de ordinul 10¹⁰ poate ajunge la 10²⁰.

Greșeli frecvente

1. Uitarea transportului final

După bucla principală, dacă transport = 1, trebuie adăugat ca cifră nouă:

if (transport > 0) {
    len = len + 1;
    c[len] = transport;
}

Fără asta, 999 + 1 = 000 (greșit) în loc de 1000.

2. Adunarea cu vectori locali neinițializați

Vectorii locali conțin gunoi dincolo de len. Adunarea iese greșită. Declară global sau folosește memset.

3. len = max(a[0], b[0]) implementat greșit

Nu uita if (b[0] > len) len = b[0]. Dacă folosești doar len = a[0], numerele mai lungi ca a sunt trunchiate.

4. Transportul poate fi 0, 1, sau mai mare?

La adunare, transportul e mereu 0 sau 1 (pentru că 9 + 9 + 1 = 19, deci transport ≤ 1). La înmulțire transportul poate fi mai mare - vezi lecția dedicată.

5. NMAX prea mic pentru sume lungi

Dacă aduni 10⁶ numere de câte 1000 cifre, suma are încă ~1006 cifre (crește foarte puțin, proporțional cu log n). Dar la înmulțiri sau puteri, lungimea crește mult mai rapid - dimensionează în consecință.

Ce să reții

• Adunare cifrică cu transport: suma = a[i] + b[i] + transport, c[i] = suma % 10, transport = suma / 10.
• Parcurgi de la 1 la max(lenA, lenB).
• La final, dacă transport > 0, adaugi încă o cifră.
• Cifrele lipsă (dincolo de un număr mai scurt) sunt 0 - automat, dacă vectorii sunt globali.
• Complexitate: O(max(lenA, lenB)).
• Adunarea poate să aliaseze (c = a) fără probleme - scriem c[i] după ce citim.
• Transportul maxim la adunare e 1 (spre deosebire de înmulțire).