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.
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];
}
}
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
}
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]--;
}
Î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ă dinb
, î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;
}
}
Î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
.
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;
Alte resurse și bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Cuprinsul lecției
Ce este un număr mare și cum se memoreazăDe ce se memorează cifrele în ordine inversă pentru numerele mari?Declararea numerelor mariInițializarea numerelor mariInițializare cu un număr micInițializare cu un număr mareAfișarea numerelor mariCompararea numerelor mariAdunarea numerelor mariScăderea numerelor mariÎnmulțirea unui număr mare cu un număr micÎnmulțirea a două numere mari28 7 14Împărțirea unui număr mare la un număr micAlte observațiiAlte operații care se pot implementaFolosirea altor baze de numerațieExerciții propuseAlte resurse și bibliografieCreează-ți un cont InfoAs și primești…
- Acces la sute de lecții de calitate, cu animații și exerciții
- Acces la peste 800 de probleme de informatică
- Indicații și rezolvări pentru fiecare problemă
- Totul 100% gratuit!
Comentarii 0