Ce sunt numerele mari?

De ce este necesar sa lucram cu numere mari? Numerele mari sunt numere ce nu pot fi stocate in tipurile de date cunoscute de noi pana acum (int, long long, etc). Daca avem o problema in care ni se cere sa adunam doua numere mari (de 500 de cifre, de exemplu), trebuie sa implementam noi operatiile generale (adunare, scadere, inmultire si impartire).

Ce solutie vom implementa?

Vom reprezenta un numar mare ca un vector in care retinem in ordine cifrele sale, incepand cu unitatile. De exemplu, numarul 123456 va fi retinut in vector astfel:

Deoarece pentru fiecare numar am avea nevoie de o variabila auxiliara care sa memoreze numarul total de cifre, apelam la un truc: memoram numarul total de cifre pe pozitia 0.

Definirea unui numar mare

#define MAX 501
typedef int NrMare[MAX];

Definim un numar mare ca fiind un vector de 501 elemente. Primul element ( NrMare[0] ) – va reprezenta numarul total de cifre ale numarului, in timp ce restul de 500 elemente vor fi cifrele efective ale numarului nostru.

Citirea si afisarea unui numar mare

void citire(NrMare x)
{
    char s[MAX];
    cin >> s;   //Citim numarul ca un sir de caractere
    int n = strlen(s);  //Calculam numarul de cifre a numarului
    for(int i = n; i >= 0; i--)
        x[n - i] = (int)(s[i] - '0'); //Retinem cifrele invers

    x[0] = n;   //Memoram numarul total de cifre
}

void afisare(NrMare x)
{
    for(int i = x[0]; i > 0; i--)
        cout << x[i];
}

Compararea a doua numere mari

Mai intai verificam daca cele doua numere sunt memorate corect: sa nu aiba zero-uri nesemnificative. De exemplu, verificam ca numarul “13” sa nu fie memorat drept “3100” (doua zerouri nesemnificative).

Dupa care parcurgem cifrele in ordinea inversa, iar atunci cand gasim o diferenta, returnam numarul mai mare.

int compara(NrMare a, NrMare b)
{
    // Eliminam zero-urile semnificative, daca exista.
    while (a[0] && !a[a[0]]) a[0]--;
    while (b[0] && !b[b[0]]) b[0]--;

    // Comparam numarul de cifre
    if (a[0] < b[0])
        return -1;
    else
        if (a[0] > b[0])
            return +1;

    // Daca numerele au un numar egal de cifre
    // Parcurgem numerele incapand cu cifra cea mai semnificativa
    // Pana la prima diferenta intalnita

    for (int i = a[0]; i > 0; --i)
    {
        if (a[i] < b[i])
            return -1;
        else
            if (a[i] > b[i])
                return +1;
    }

    // Cazul final: cele doua numere sunt egale
    return 0;
}

Suma a doua numere mari

Pentru a calcula suma a doua numere mari, trebuie mai intai sa ne asiguram ca amandoua au acelasi numar de cifre. De exemplu, daca vrem sa adunam numerele 124 si 96, cele doua vor arata in memorie astfel:

Daca numarul nostru y era mai mic, evident, adaugam mai multe 0-uri nesemnificative. Dupa aceasta vom parcurge simultan cele doua numere,incepand de la unitati. Vom aduna cele doua cifre de pe pozitii corespondente si vom lua in calcul si eventuala cifra in plus care s-a obtinut de la adunarea precedenta. Retinem in suma cifra obtinuta prin adunare si recalculam cifra in plus.

Suma ar putea avea o cifra in plus fata de cel mai mare dintre cele doua numere (daca la sfarsit cifra in plus este nenula). Functia suma() va avea ca parametri cele doua numere mari care se aduna si numarul mare rezultat.

void suma(NrMare a, NrMare b, NrMare rezultat)
{
    int t = 0, max;

    //  Completam numarul cel mai mic cu zeroouri nesemnificative
    if(a[0] < b[0])
    {
        max = b[0];
        for(int i = a[0] + 1; i <= b[0]; i++)
            a[i] = 0;
    }
    else
    {
        max = a[0];
        for(int i = b[0] + 1; i <= a[0]; i++)
            b[i] = 0;
    }

    int i;
    for(i = 1; i <= max; i++)
    {
        int cifra = a[i] + b[i] + t;
        rezultat[i] = cifra % 10;
        t = cifra/10;
    }

    if(t)
        rezultat[i] = t;
    else
        i--;

    rezultat[0] = i;
}

Diferenta a doua numere mari

Vom presupune ca descazutul este mai mare sau egal cu scazatorul.Pentru a calcula diferenta a doua numere mari vom parcurge dezcazutul incepand de la unitati. Vom scadea din cifra curenta a descazutului cifra curenta a scazatorului si vom lua in calcul si eventuala cifra de transport, obtinuta la scaderea precedenta. Daca rezultatul este negativ, imprumutam 10 de pe pozitia urmatoare (este posibil doar daca descazutul este mai mare ca scazatorul), si in acest caz cifra de transport devine -1.

Diferenta ar putea avea mai putine cifre decat descazutul, astfel incat la sfarsit calculam numarul de cifre din diferenta, ignorand zerourile nesemnificative.

void diferenta(NrMare a, NrMare b, NrMare rezultat)
{
    if(a[0] < b[0])
        diferenta(b, a, rezultat);
    else
    {
        int i, t = 0;
        for(i = 1; i <= a[0]; i++)
        {
            rezultat[i] = a[i] - b[i] + t;
            if(rezultat[i] < 0)
            {
                rezultat[i] += 10;
                t = -1;
            }
            else
                t = 0;
        }
        i--;
        while(i && !rezultat[i])
            i--;
        rezultat[0] = i;
    }
}