Pe scurt
Numerele mari sunt valori care depășesc capacitatea tipurilor de date standard și se stochează ca șiruri de caractere. Operațiile aritmetice se realizează manual, cifră cu cifră, similar algoritmilor din școală, iar gestionarea transporturilor și eliminarea zerourilor de la început sunt aspecte esențiale.
Reprezentarea numerelor mari ca șiruri de caractere
- Numerele mari nu pot fi reprezentate în tipurile de date standard (int, long long etc.) din cauza dimensiunii lor
- În programare, pentru a manipula astfel de numere, le stocăm ca șiruri de caractere (string-uri), unde fiecare caracter reprezintă o cifră
- În practică, se folosește un vector de int-uri (sau listă) pentru a stoca cifrele în ordine inversă (cifra unităților pe prima poziție), simplificând gestionarea transporturilor
Algoritmul de adunare cu transport
- Adunarea se face cifră cu cifră, de la dreapta la stânga, ținând cont de transport
- Exemplul 1: Adunarea a două numere mari. Fie a = „999” și b = „1”. Algoritmul: se parcurg cifrele de la dreapta la stânga. Cifre: 9+1=10, se scrie 0, transport=1; următoarea: 9+0+1=10, scrie 0, transport=1; ultima: 9+0+1=10, scrie 0, transport=1. Se adaugă transportul final => rezultat „1000”
- De exemplu, pentru a aduna „123” și „456”, aliniem cifrele și adunăm: 3+6=9, 2+5=7, 1+4=5, obținând 579
- Dacă suma depășește 9, reținem transportul
Algoritmul de înmulțire cu produse parțiale
- Înmulțirea este mai complexă: se înmulțește fiecare cifră a primului număr cu fiecare cifră a celui de-al doilea
- Rezultatele se plasează la pozițiile corespunzătoare (similar înmulțirii pe hârtie), apoi se adună toate produsele parțiale
- Un aspect important este gestionarea transporturilor și eliminarea zerourilor de la începutul rezultatului (leading zeros)
- Exemplul 2: Înmulțirea unui număr mare cu o cifră. Fie a = „123” și b = „4”. Se parcurge a de la dreapta la stânga: 3*4=12, scrie 2, transport=1; 2*4+1=9, scrie 9, transport=0; 1*4=4, scrie 4. Rezultat: „492”
- Exemplul 3: Înmulțirea a două numere mari. Fie a = „12” și b = „34”. Se face produsul fiecărei cifre: 2*4=8 (scris la poziția 0), 2*3=6 (poziția 1), 1*4=4 (poziția 1), 1*3=3 (poziția 2). Adunăm produsele parțiale: 8 (poziția 0), 6+4=10 (poziția 1, scrie 0, transport 1), 3+1=4 (poziția 2). Rezultat: „408”
Complexitatea algoritmilor
- Algoritmii au complexitate **O(n*m) pentru adunare și O(n*m) pentru înmulțire, unde n și m** sunt lungimile șirurilor
Verifică-te!
- Cum se stochează numerele mari în programare și de ce?
- Ce se întâmplă când suma a două cifre depășește 9 în algoritmul de adunare?
- Care este complexitatea algoritmilor de adunare și înmulțire pentru numere mari?