Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Operații cu numere mari în C++ - Toate funcțiile explicate

Există situații în care vrem să memorăm în limbajele de programare precum C++ numere întregi foarte mari (cu sute de cifre, de exemplu), iar în aceste situații, tipuri de date int și long long nu sunt destul de încăpătoare pentru a memora astfel de valori (de pildă, long long reține până la 19 cifre).

Din această nevoie a apărut conceptul de numere mari, adică o modalitate de a reține valori uriașe și de a efectua operații aritmetice cu acestea (precum adunarea, scăderea, înmulțirea, împărțirea, etc.). Vom numi în continuare scalar/număr mic un număr obișnuit, de tip int sau long long.

Operațiile aritmetice sunt ca cele din clasele primare, așadar se pot memora ușor logic, însă le vom și explica în această lecție. Fiecare operație va fi o funcție, pentru a le putea apela unde vrem în program cu ușurință.

Ce este un număr mare și cum se memorează

Un număr mare este defapt un vector de cifre ce reține un număr natural. Mai precis, dacă a[] este un număr mare, salvăm pe poziția a[0] lungimea sa (numărul de cifre ale sale), iar pe pozițiile 1, 2, 3, …, a[0] memorăm cifrele sale în ordine inversă.

Spre exemplu, dacă am vrea să memorăm numărul 302561, vectorul ar arăta în felul următor:

i 0 1 2 3 4 5 6
a[i] 6 1 6 5 2 0 3

Se respectă structura menționată mai devreme: avem a[0] = 6 cifre, cifra unităților este 1, cifra zecilor este 6, cifra sutelor este 5 și așa mai departe.

De ce se memorează cifrele în ordine inversă pentru numerele mari?

Motivul pentru care se memorează cifrele în ordine inversă este că se gestionează mult mai ușor în acest fel. Este mult mai ușor să știm mereu că pe poziția 1 reținem cifra unităților, pe poziția 2 reținem cifra zecilor și așa mai departe — altfel, cifrele acestea ar depinde de lungimea numărului, ceea ce este mai complicat.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Declararea numerelor mari

Pentru a declara un număr mare, creăm pur și simplu un vector, unde lungimea depinde de numărul de cifre. Crearea unui număr mare de lungime 1000 este:

int numarMare[1003];

Unii preferă să creeze propria structură de date cu numere mari. Așadar, o alternativă este:

typedef int numarMare[1003];
…
numarMare a; //a este acum un vector număr mare cu 1000 de cifre

Inițializarea numerelor mari

Un număr mare poate fi inițializat în două moduri.

Inițializare cu un număr mic

Dacă avem un număr mic într-un int și vrem să îl punem într-un număr mare, avem următoarea funcție:

void atribuire_nrmic(int a[], int b) {
    //a <- b
    a[0] = 0;
    do {
        int cif = b % 10;
        b = b / 10;
        a[0]++;
        a[a[0]] = cif;
    } while(b != 0);
}

Practic, resetăm lungimea numărului mare a cu 0, iar cât timp b are cifre (folosind proprietățile cifrelor unui număr), punem ultima cifră a lui b pe poziția ultimei cifre a lui a, cifra zecilor și așa mai departe.

Inițializare cu un număr mare

Dacă avem un număr mare b și vrem să îl duplicăm într-un alt număr a, avem următoarea funcție, care pur și simplu copiază tot vectorul dintr-unul în altul:

void atribuire_nrmare(int a[], int b[]) {
    //a <- b
    a[0] = b[0];
    for(int i = 1; i <= a[0]; i++) {
        a[i] = b[i];
    }
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Afișarea numerelor mari

Funcția de afișare a numerelor mari este foarte simplă: afișăm cifrele din vector, însă în ordine inversă, de la prima cifră către ultima:

void afisare_nrmare(int a[]) {
    for(int i = a[0]; i >= 1; i--) {
        cout << a[i];
    }
}

Compararea numerelor mari

Compararea a două numere mari este simplă, exact ca cea învățată în clasele mici:

  • dacă un număr are mai multe cifre decât celălalt, atunci este mai mare;
  • dacă au același număr de cifre, se compară cifrele începând cu cele mai semnificative, până la ultima cifră; dacă toate sunt egale, atunci cele două numere sunt egale, altfel deducem care este mai mare.

Funcția de comparare a două numere mari returnează 0 dacă numerele sunt egale, 1 dacă primul număr este mai mare și -1 dacă al doilea număr este mai mare. Trebuie la început să ne asigurăm că vectorii memorează corect numărul de cifre (mai precis, că nu avem cifre de 0 la început, de pildă la numărul 00123 = 123, lucru ce se poate întâmpla în timpul programului):

int comparare_nrmare(int a[], int b[]) {
    //a == b -> 0  |  a > b -> 1  |  a < b -> -1
    while(a[0] > 1 && a[a[0]] == 0) //avem cel puțin o cifră, iar prima cifră este 0
        a[0]--;
    while(b[0] > 1 && b[b[0]] == 0)
        b[0]--;

    if(a[0] > b[0]) return 1;
    else if(a[0] < b[0]) return -1;

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

    return 0; //numerele sunt egale
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Adunarea numerelor mari

Funcția de adunare așteaptă două numere a și b (cu număr variabil de cifre) și salvează, la final, în a, suma dintre a și b. Suma este ca cea din clasele primare: luăm cifrele de la coadă la cap și adunăm cifrele pe rând. Dacă cifra curentă este 10 sau mai mult, atunci trebuie adunat 1 la următoarea cifră, iar pe poziția curentă luăm ultima cifră a sumei cifrelor. Pentru a evita posibilele erori, pentru numărul cu mai puține cifre, completăm cifrele de după cu 0. Iată funcția:

void adunare_nrmare(int a[], int b[]) {
    //a <- a + b
    int lungime;
    if(a[0] > b[0]) lungime = a[0];
    else lungime = b[0];

    for(int i = a[0] + 1; i <= lungime; i++)
        a[i] = 0;
    for(int i = b[0] + 1; i <= lungime; i++)
        b[i] = 0;

    a[0] = lungime;
    int t = 0;
    for(int i = 1; i <= a[0]; i++) {
        a[i] = a[i] + b[i] + t;
        t = a[i] / 10;
        a[i] = a[i] % 10;
    }
    //este posibil să rămânem cu cifre în plus de adăugat (exemplu 999 + 1 = 1000, nu 000)
    if(t != 0) {
        a[0]++;
        a[a[0]] = t;
    }
}

Scăderea numerelor mari

Similar, scăderea se face cifră cu cifră începând cu ultima. În acest caz, presupunem din start că b ≤ a, pentru că lucrăm cu numere naturale (putem verifica cu funcția comparare_nrmare). Din nou, avem un transport t, care asigură scăderi peste ordin (de pildă 1000 - 1 = 999):

void scadere_nrmare(int a[], int b[]) {
    //a <- a - b

    for(int i = b[0] + 1; i <= a[0]; i++)
        b[i] = 0;

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

    while(a[0] > 1 && a[a[0]] == 0) //dacă mai avem cifre de 0 la coadă, de exemplu 1000 - 1 = 0999 = 999
        a[0]--;
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Înmulțirea unui număr mare cu un număr mic

Înmulțirea cu un număr mic se face la fel, ca în clasele mici. Când numărul mic are o singură cifră, rezultatul este simplu, iar un lucru interesant este că funcția merge și când numărul mic are mai mult de o cifră (funcționează la fel). Trebuie doar să ținem cont că transportul poate avea mai mult de o cifră, așadar, la final, în loc să verificăm cu un if dacă transportul este gol sau nu, verificăm cu un while, extragând mereu ultima cifră.

void inmultire_nrmic(int a[], int b) {
    // a <- a * b
    int t = 0;
    for(int i = 1; i <= a[0]; i++) {
        a[i] = a[i] * b + t;
        t = a[i] / 10;
        a[i] = a[i] % 10;
    }

    while(t != 0) {
        a[0]++;
        a[a[0]] = t % 10;
        t /= 10;
    }
}

Înmulțirea a două numere mari

Înmulțirea a două numere mari a și b se face, la fel, ca în clasele mici. Algoritmul în acest caz este mai dificil de înțeles, deci să vedem cum funcționează:

  • luăm numerele inițiale și le așezăm unul sub celălalt, ca în clasele mici:
      4   1   2  ×
          7   4
  • înmulțim fiecare cifră din a cu fiecare cifră din b, însă așezăm rezultatele deplasate, ca mai jos:
      4   1   2  ×
          7   4 
----------------
     16   4   8
 28   7  14
  • calculăm sumele de pe fiecare coloană:
      4   1   2  ×
          7   4 
----------------
     16   4   8
 28   7  14    
----------------
 28  23  18   8
  • ca la sumă, corectăm rezultatul, mutând cifrele peste 9 cu o poziție spre stânga:
         4   1   2  ×
             7   4 
-------------------
        16   4   8
    28   7  14    
-------------------
    28  23  18   8
-------------------
 3   0   4   8   8

Vedem că numărul de cifre ale rezultatului este în jur de a[0] + b[0] - 1 (depinzând de transport). Pentru ușurință, memorăm rezultatul într-un al treilea număr mare, c.

void inmultire_nrmare(int a[], int b[], int c[]) {
    //c <- a * b
    c[0] = a[0] + b[0] - 1;
    for(int i = 1; i <= a[0] + b[0]; i++) //golim vectorul c
        c[i] = 0;

    for(int i = 1; i <= a[0]; i++) {
        for(int j = 1; j <= b[0]; j++) {
            c[i + j - 1] += a[i] * b[j];
        }
    }

    int t = 0;
    for(int i = 1; i <= c[0]; i++) {
        c[i] = c[i] + t;
        t = c[i] / 10;
        c[i] = c[i] % 10;
    }

    if(t != 0) {
        c[0]++;
        c[c[0]] = t;
    }
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Împărțirea unui număr mare la un număr mic

Operația de împărțire este similară ca algoritmul de pe hârtie (învățat în casele mici). Luăm cifrele începând cu prima, găsim restul curent și calculăm rezultatul. Funcția întoarce restul și salvează în numărul mare câtul împărțirii întregi:

int impartire_nrmic(int a[], int b) {
    //a <- a / b  |  se returnează restul
    int r = 0;
    for(int i = a[0]; i >= 1; i--) {
        r = r * 10 + a[i];
        a[i] = r / b;
        r = r % b;
    }

    while(a[0] > 1 && a[a[0]] == 0) {
        a[0]--;
    }

    return r;
}

Alte observații

Alte operații care se pot implementa

Bazat pe operațiile menționate mai sus, se pot implementa alte operații mai complexe (ridicarea la putere, ridicarea la putere în timp logaritmic, împărțitrea a două numere mari, înmulțiri și împărțiri mai eficiente cu 10 și multe altele).

Cu toate acestea, numerele mari nu se folosesc foarte des, iar în situațiile în care se folosesc, numerele rezultat de obicei se construiesc doar cu operațiile menționate mai devreme.

Folosirea altor baze de numerație

Toate operațiile pe care le-am menționat mai sus folosesc operații în baza 10, bază pe care o folosim în viața de zi cu zi. Cu toate acestea, nu este o necesitate să folosim această bază, dacă folosim operații cu alt număr în loc de 10. De pildă, folosind o bază precum baza 100, 1000, …, putem să facem operațiile mai rapid, însă în detrimentul simplității. Trebuie avut grijă ca baza pe care o folosim în acest caz și operațiile folosite să nu depășească tipul de date int, deoarece numerele mari sunt vectori de numere int.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Exerciții propuse

Completează următoarele secvențe de cod:

Să se elimine prima cifră a numărului mare a:

a[???]--;

Să se calculeze suma cifrelor numărului mare a în s:

int s = 0;
for(int i = ???; i <= a[0]; i++) {
    s += a[???];
}
cout << s;

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Alte resurse și bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Numărul de divizori al unui număr în C++Verificare dacă un număr este palindrom în C++Transformarea unei litere mici în literă mare în C++Numărul de cifre ale factorialului unui numărIndicatorul lui Euler în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiVerifică dacă un caracter este cifră în C++Verificare număr prim în C++ (Clasa a IX-a)Bordarea unei matrice în C++Verifică dacă un număr este par sau impar fără modulo în C++Ce este o variabilă unsigned în C++?Verificare dacă șir de caractere este palindrom în C++Operații cu numere mari în C++ - Toate funcțiile explicateTutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Do while vs while în C++ - Care e diferența?Verifică dacă o literă este vocală în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortOglinditul recursiv al unui număr în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Maximul și minimul a două valori în C++Funcții în C++. Ce sunt subprogrameleCel mai semnificativ bit în C++Inversarea unui vector în C++Cel mai mic număr cu suma cifrelor N în C++Maximul și minimul a n valori în C++Aflarea sumei primelor N sume GaussMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleCum să citești și să afișezi în fișiere în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Cel mai mare divizor comun (CMMDC) a două numere în C++Suma numerelor naturale dintr-un interval dat în C++Interclasarea a doi vectori în C++Ce înseamnă endl în C++?Algoritm recursiv pentru căutare binară (clasa a X-a)Afișarea elementelor unui vector recursiv în C++Inversarea unui șir de caractere în C++Ciurul lui Eratostene în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăVerifică dacă o literă este mică sau mare în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Tipul struct în C++. Ce sunt structurile de date neomogeneVectorii în C++: citire și afișareTransformarea unui număr din baza 2 în baza 10 în C++Recursivitate în C++Numărul de apariții al unui număr într-un vector în C++Numărul minim de peroane pentru o gară în C++Cifra maximă și minimă a unui număr în C++Instrucțiunea while (structuri repetitive)Oglinditul unui număr în C++Afișarea divizorilor primi ai unui număr în C++Structuri repetitive (while, do while, for, etc)Al N-lea termen dintr-o progresie aritmeticăDivide et Impera (metodă de programare C++)Valoarea absolută (modulul) unui număr în C++Pointer în C++. Variabile de tipul char * (char steluță)Aria unui triunghi folosind coordonatele acestora în C++Citește un șir de caractere cu spații în C++Codul ASCII (tabel complet)Radicalul unui număr în C++ (rădăcina pătrată)Al N-lea termen dintr-o progresie geometricăCe înseamnă variabilă globală și locală în C++?Factorialul unui număr în C++Complexitatea unui algoritm (timp și spațiu) în C++Matrice pătratice în C++. Diagonala principală și secundarăSuma 1 + 2 + 3 + ... + N în C++Aria și circumferința unui cerc în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Interschimbarea a două variabile în C++ (3 metode)Cum să calculezi instant 2 la puterea N în C++Transformarea unui număr din baza 10 în baza 2 în C++Transformarea unei litere mari în literă mică în C++Suma divizorilor unui număr în C++Verifică dacă un caracter este literă în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Prima cifră a unui număr în C++Verifică dacă un număr dat este o putere de 2 în C++CMMDC recursiv a două numere naturale în C++Comentarii în C++Instrucțiunea for (structuri repetitive)Câte numere naturale sunt într-un interval dat? (C++)Citirea și afișarea matricelor în C++Verifică dacă un număr aparține șirului Fibonacci în C++Ce este o funcție void în C++?Instrucțiunea continue (structuri repetitive)Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cifra maximă a unui număr recursiv în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorCifra de control a unui numărNumărul de divizori primi ai unui număr în C++Numere triunghiulare. Verificarea unui număr triunghiularȘiruri de caractere în C++. Tot ce trebuie să știiAflă secolul unui an citit de la tastatură în C++Căutare binară în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Instrucțiunea do while (structuri repetitive)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Tipuri de date în C++: numere întregi, reale, caractere și alteleCea mai lungă secvență de elemente crescătoare în C++Suma elementelor unui vector recursiv în C++Cel mai puțin semnificativ bit în C++Rădăcina cubică a unui număr în C++ (cube root)Verificarea unui an bisect în C++Vectorii în C++: declarare și parcurgereGenerarea șirului Fibonacci generalizat în C++Cum să afișezi partea întreagă a unui număr real în C++Distanța dintre două puncte în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleNumărul permutărilor în C++ (formula permutărilor)Copiuțe: Cifrele unui numărVerifică dacă trei puncte sunt coliniare C++Șirul lui Fibonacci în C++Calculul combinărilor de n luate câte k (nCk) în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicMediana unui șir de valori în C++Instrucțiunea break (structuri repetitive)Vectori de frecvență (de apariții) în C++Maximul și minimul a trei valori în C++Maximul și minimul unui vector în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Al N-lea termen Fibonacci în C++Cel mai frecvent element dintr-un șir în C++Numărul combinărilor în C++ (formula combinărilor)Instrucțiunea de decizie în C++: if, else, switch, case

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont