Etichete : algoritmica, C++, numere mari, operatii

In urmatorul articol voi prezenta principalele operatii cu numere mari,cum ar fi :

0. De ce este necesara implementarea operatiilor cu numere mari?
1. Citirea unui numar mare
2. Afisarea unui numar mare
3. Suma a doua numere mari
4. Diferenta a doua numere mari
5.Produsul a doua numere mari
6.Compararea a doua numere mari
7. Inmultirea unui numar mare cu o putere a lui 10
9. Exemplu de folosire
10. Exercitii

0. De ce este necesara implementarea operatiilor cu numere mari?

Sa consideram numerele naturale mari(cu maximum 500 de cifre).Nici unul dintre tipurile limbajului C/C++ nu permite lucrul cu astfel de numere.Prin urmare,trebuie sa implementam propriul nostru tip pentru numere mari si operatiile uzuale cu acest tip de numere(adunare,scadere,inmultire,impartire,comparare).

0.1 Solutie?

Vom reprezenta un numar natural mare ca un vector in care retinem in ordine cifrele sale,incepand cu unitatile(astfel pe pozitia 0 se va afla cifra unitatilor,pe pozitia 1 cifra zecilor s.a.m.d).
Insa pentru aceasta solutie, pentru fiecare numar vom avea nevoie de o variabila auxiliara care sa contorizeze numarul de cifre ale numarului nostru mare.Pentru rezolvarea acestei probleme pe pozitia 0 se va afla acest numar,iar pozitiile cifrelor vor incepe de pe pozitia 1.

#define LG_MAX 500 + 1 // avem nevoie de acel 1 pentru a satisface si necesitatea lunigimii sirului de cifre
typedef int BigNumber[LG_MAX];

1. Citirea unui numar mare

Pentru a citi un numar mare vom citi de la tastatura numarul intr`un sir de caractere,apoi vom transforma caracterele in numere si le vom memora in ordine inversa in vectorul cu cifrele numarului mare.Pentru a usura calculele,vom completa zona de memorie alocata numarului mare(celelalte componente ale vectorului de cifre) cu 0.Functia citire() va avea un singur parametru : vectorul in care retinem cifrele numarului mare citit(BigNumber x) si numarul cifre ale respectivului numar.

2. Afisarea unui numar mare

Vom parcurge vectorul de cifre de la sfarsit catre inceput,afisand succesiv cifrele.Functia de afisare va avea un singur parametru (vectorul in care retinem cifrele numarului mare citit si numarul de cifre ale numarului mare).

3. Suma a doua numere mari

Pentru a calcula suma a doua numere mari 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 de transport care s`a obtinut de la adunarea precedenta.Retinem in suma cifra obtinuta prin adunare si recalculam transportul.Suma ar putea avea o cifra in plus fata de cel mai mare dintre cele doua numere(daca la sfarsit cifra de transport este nenula).
Functia suma() va avea ca parametri cele doua numere mari care se aduna si numarul mare rezultat.

4. 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.

5. Produsul a doua numere mari

Vom initializa vectorul de cifre ale produsului cu 0.Vom inmulti fiecare cifra a inmultitorului(b) cu deinmultitul(a) si vom aduna acest produs partial obtinut la produs(ale carui cifre sunt memorate in vectorul p).Observati ca atunci cand inmultim cifra b[j] cu a, produsul partial obtinut este inmultit cu 10^j(adica cifrele sunt deplasate cu j pozitii la dreapta).

6. Compararea a doua numere mari

Daca numarul de cifre din a este mai mic decat numarul de cifre din b,atunci a < b(si invers).Daca numerele a si au acelasi numar de cifre ,atunci parcurgem cele doua numere simultan,incepand de la cifra cea mai nesemnificativa pana la intalnirea a doua cifre diferite.Dca am intalnit doua cifre diferite,ele determina ordinea dintre a si b;in caz contrar numerele sunt egale.

7. Inmultirea unui numar mare cu o putere a lui 10

Pentru a inmulti un numare cu 10^nr trebuie sa deplasam cifrele numarului cu nr pozitii la dreapta si sa completam in stanga cu zerouri.

8. Impartirea a doua numere mari

Daca cele doua numere mari sunt comparabileca dimensiune,putem simula impartirea prin scaderi repetate; in caz contrar,aceasta metoda este ineficienta.Vom simula algorimtul de impartire invatat la matematica.

9. Exemplu de folosire

Tot ce trebuie sa faceti este sa implementati una din functiile prezentate anterior.Aici veti avea doar sabloanele lor.

#include<stdio.h>
#include<string>

#define LG_MAX 500 + 1
typedef int BigNumber[LG_MAX];

void citire(BigNumber x);
void afisare(BigNumber x);
void suma(BigNumber a,BigNumber b,BigNumber s);
void diferenta(BigNumber a,BigNumber b,BigNumber d);
void produs(BigNumber a,BigNumber b,BigNumber p);
int compara(BigNumber a,BigNumber b);
void p10(BigNumber x,int nr);
void div(BigNumber a,BigNumber b,BigNumber c,BigNumber r);

int main()
{
    freopen("operatii.in","r",stdin);
    freopen("operatii.out","w",stdout);

    BigNumber nr1,nr2,s;

    citire(nr1);  //citim primul numar
    citire(nr2);  //citim al doilea numar
    produs(nr1,nr2,s); //calculam produsul celor 2 numere in s
    afisare(s);  //afisam

    fclose(stdin); fclose(stdout);
    return 0;
}

Sursa completa o gasiti aici : Operatii cu numere mari

10. Exercitii

1. Pe baza articolului de mai sus incercati implementarea numerelor mari de mai multe cifre(30000)
2. Incercati implementarea acestor functii fara ca prima pozitie din vector sa reprezinte lungimea numarului.

Cam atat in acest articol,daca observati erori de sintaxa va rog nu ezitati sa ma atentionati.

Link-uri externe :
Lucrul cu numere mari

Recomandam, pe aceeasi tema

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 591 articole (vezi lista completa).

Contact | andrei@worldit.info | @worldIT – @AndreiAvadanei

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.