Pe scurt
Numerele mari depășesc capacitatea tipurilor de date standard (int, long long) și necesită reprezentări alternative, precum stocarea într-un șir de caractere sau într-un vector de cifre. Operațiile aritmetice pe aceste numere se implementează manual, similar algoritmilor din școala primară, folosind bucle și gestionarea transportului (carry) sau a împrumutului (borrow). Aceste tehnici sunt esențiale pentru rezolvarea problemelor de la Bacalaureat și în competiții, permițând manipularea numerelor extrem de mari, cum ar fi factorialul unui număr.
Reprezentarea numerelor mari
Numerele mari sunt numere care depășesc capacitatea tipurilor de date standard (
int,
long long) din limbajele de programare. De exemplu, în C++, un
int poate stoca valori până la aproximativ 2.147.483.647, iar un
long long până la 9.223.372.036.854.775.807. Pentru a lucra cu numere mult mai mari (de exemplu, 10^100), avem nevoie de reprezentări alternative.
Cea mai comună metodă este stocarea numărului ca un șir de caractere (string) sau într-un vector (array) de cifre. Fiecare cifră a numărului este stocată într-un element al vectorului, de obicei în ordine inversă (de la cifra unităților la cifra cea mai semnificativă) pentru a ușura operațiile aritmetice.
Operații pe numere mari
Operațiile pe numere mari (
adunare,
scădere,
înmulțire,
împărțire) se realizează manual, similar algoritmilor învățați în școala primară, dar implementați sub formă de bucle și gestionare a
transportului (carry) sau a
împrumutului (borrow).
Adunarea numerelor mari
Pentru adunarea a două numere mari, se parcurg cifrele de la dreapta la stânga, se adună cifrele corespunzătoare împreună cu transportul, iar rezultatul se stochează într-un nou vector.
- Exemplul 1: Adunarea a două numere mari. Să adunăm 12345678901234567890 și 98765432109876543210. Se reprezintă fiecare număr ca string, se inversează, se adună cifră cu cifră cu transport, rezultatul este 111111111011111111100.
Înmulțirea numerelor mari
Pentru înmulțire, se folosește un algoritm asemănător înmulțirii pe hârtie, unde fiecare cifră a primului număr este înmulțită cu fiecare cifră a celui de-al doilea, iar rezultatele se însumează cu deplasare.
- Exemplul 2: Înmulțirea unui număr mare cu un număr mic. Să înmulțim numărul 99999999999999999999 cu 7. Se parcurg cifrele de la dreapta la stânga, se înmulțește fiecare cifră cu 7, se adună transportul, rezultatul este 699999999999999999993.
- Exemplul 3: Calculul factorialului unui număr. Factorialul lui 100 (100!) are 158 de cifre. Algoritmul: se inițializează un vector cu 1, apoi pentru i de la 2 la 100, se înmulțește vectorul cu i (similar înmulțirii cu număr mic), gestionând transportul. Rezultatul este un număr imens.
Aspecte practice și optimizare
Aceste tehnici sunt esențiale în rezolvarea problemelor de la
Bacalaureat și în
competiții, deoarece permit manipularea numerelor extrem de mari, cum ar fi factorialul unui număr sau calculul unor puteri uriașe. De asemenea, este important să gestionăm eficient
memoria și să evităm
overflow-ul prin utilizarea unui vector dinamic.
În plus, trebuie acordată atenție optimizării: de exemplu, la înmulțire se poate folosi algoritmul Karatsuba pentru numere foarte mari, dar pentru nivel liceal, algoritmul clasic este suficient. În concluzie, numerele mari nu sunt altceva decât o modalitate de a extinde capacitățile calculatorului prin programare, iar înțelegerea acestor concepte deschide calea către algoritmi avansați și probleme complexe.
Concepte cheie
- Reprezentarea numerelor mari în vectori sau stringuri
- Algoritmul de adunare cu transport (carry)
- Înmulțirea numărului mare cu un număr mic
Verifică-te!
- Care este cea mai comună metodă de reprezentare a numerelor mari și în ce ordine se stochează cifrele?
- Cum se realizează adunarea a două numere mari la nivel de algoritm?
- Ce reprezintă transportul (carry) în contextul operațiilor pe numere mari?